파일 업로드

파티 준비

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

서연이의 N명의 친구들 (1 <= N <= 10,000)은 1..N으로 번호가 매겨져 있으며, 파티 준비를 위해 각각 업무를 맡았습니다. 각 친구 i는 일을 완료하는 데 T(i)단위의 시간이 걸립니다. 그리고 일부 일은 다른 일이 완료되기 전에 시작될 수 없습니다. 친구 A가 친구 B보다 먼저 일을 완료해야한다면, 친구 A의 일이 완전히 완료될 때까지 친구 B의 일을 시작할 수 없습니다.

서연이는 파티 준비를 빨리 끝내기 위해 여러 명의 친구들을 동시에 일을 시킬 수 있습니다. 동시에 일을 진행할 순 있지만 일부 일이 다른 일보다 먼저 완료되어야하는 제약 조건이 있어 빨리 끝내는 데 제한이 있습니다.

서연이 전체 작업이 완료되는 데 걸리는 최소 시간을 계산하는 것을 도와주십시오.

💻 입력
  • 첫 번째 줄 : 두 개의 띄어쓰기로 구분된 정수 : N (친구의 수) 와 M (일 제한의 수; 1 <= M <= 50,000).
  • 두 번째 줄..1+N : 라인 i+1에는 T(i)의 값이 있습니다 (1 <= T(i) <= 100,000).
  • 2+N 번째 줄..1+N+M 번째 줄 : 각 줄은 A 와 B 두 개의 띄어쓰기로 구분된 정수를 포함하며, 이는 친구 A가 완전히 일을 완료하고 나서야 친구 B가 일을 시작할 수 있다는 것을 나타냅니다. 이러한 제한 사항들은 결코 순환을 형성하지 않으므로 언제나 해결책이 가능합니다.
🖨️ 출력
  • 첫 번째 줄 : 모든 친구가 일을 완료하는데 필요한 최소 시간.

💻 예제 입력 1
3 1
10
5
6
3 2
🖨️ 예제 출력 1
11

출처: USACO 2013 February Contest, Silver Problem 3. Milk Scheduling