1717 . 專案時程
TopCoder
Tags
Description
通常在開發一個專案時，整個專案會被分割為許多個項目，並同時分配給多組程式設計師去開發。
但這些項目是有順序關係的，只有當順序在前方的項目完成後，才能夠開始開發順序在後方的項目。
我們利用一個有向圖，來表示這些項目的開發順序。圖上的每一個節點代表一個項目，
節點內的數字為節點編號，上方的數字代表開發這個項目所需的天數；
圖上的邊則表示開發的順序，以下圖為例，只有在節點 2 完成後，才能夠開始節點 4 的開發。
下圖為範例測試資料中的第二組專案有向圖。
有一間軟體公司目前正有許多的專案準備開始開發，
但是這間公司的前一任專案管理人(PM)因不堪壓力離職了，在臨走之前他留下了當初粗略畫出的開發流程圖。
現在你是這間公司新進的專案管理人，而你的老闆正迫切的想知道這些專案能不能在他所限制的時間內完工，
請你寫一個程式依照這些專案的開發流程圖回答老闆的問題。
註: 這間公司有非常充足的程式設計師，因此並不需要擔心人手不夠的問題。
| 每一行輸入資料 | 說明 |
| 2 | 共有兩組專案測試資料 |
| 2 | 第一組專案有兩個工作項目（節點） |
| 8 1 2 | 第一個工作項目需要 8 天才能完成，有一個工作項目（第二個工作項目）需等第一個工作項目完成後才能進行。 |
| 2 0 | 第二個工作項目需要 2 天才能完成 |
| 5 | 第二組專案有五個工作項目（節點） |
| 6 2 2 3 | 第一個工作項目需要 6 天才能完成，有兩個工作項目（第二、三個工作項目）需等第一個工作項目完成後才能進行。 |
| 5 1 4 | 第二個工作項目需要 5 天才能完成，有一個工作項目（第四個工作項目）需等第二個工作項目完成後才能進行。 |
| 11 1 5 | 第三個工作項目需要 11 天才能完成，有一個工作項目（第五個工作項目）需等第三個工作項目完成後才能進行。 |
| 4 1 5 | 第四個工作項目需要 4 天才能完成，有一個工作項目（第五個工作項目）需等第四個工作項目完成後才能進行。 |
| 8 0 | 第五個工作項目需要 8 天才能完成 |
Input Format
輸入的第一行有一個整數，代表後續測試資料組數。
每組測試資料代表一個專案的有向圖，
在每組測試資料的第一行有一個正整數N，代表這個專案共有 N 個工作事項（節點） ，N≤1000。
接下來有N 行測試資料，每一行依序代表一個項目節點(從 1 開始)，
第一個正整數表示完成這個項目所需的天數，第二個正整數 K 表示這個節點有 K 條指向其他節點的邊，
接下來 K 個正整數表示所指向的項目節點編號。
註：專案的有向圖不一定都會是連結在一起的。
Output Format
對於每組測試資料輸出完成該專案所需的最少天數。
Sample Input 1
2
2
8 1 2
2 0
5
6 2 2 3
5 1 4
11 1 5
4 1 5
8 0
2
8 1 2
2 0
5
6 2 2 3
5 1 4
11 1 5
4 1 5
8 0
Sample Output 1
10
25
25
Hints
本題保證所有計算過程都不會超出32位元有號整數。
Problem Source
原TIOJ1717 / TOI2010初選(prob 2)。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 20 |
| 2 | 1 | 20 |
| 3 | 2 | 20 |
| 4 | 3 | 20 |
| 5 | 4 | 20 |