|Online Judge||Problem Set||Authors||Online Contests||User|
There are n preemptive jobs to be processed on a single machine. Each job j has a processing time pj and deadline dj. Preemptive constrains are specified by oriented graph without cycles. Arc (i,j) in this graph means that job i has to be processed before job j. A solution is specified by a sequence of the jobs. For any solution the completion time Cj is easily determined.
The objective is to find the optimal solution in order to minimize
The first line contains a single integer n, 1 ≤ n ≤ 50000. Each of the next n lines contains two integers pj and dj, 0 ≤ pj ≤ 1000, 0 ≤ dj ≤ 1000000, separated by one or more spaces. Line n+2 contains an integer m (number of arcs), 0 ≤ m ≤ 10*n. Each of the next m lines contains two integers i and j, 1 ≤ i, j ≤ n.
Each of the n lines contains integer i (number of job in the optimal sequence).
2 4 1 4 0 1 1 2
Northeastern Europe 2003, Western Subregion
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator