2232 . 犯罪現場調查
TopCoder
Tags
Description
TOI 國最近發生了一件重大刑案！警方經過初步的調查，將嫌犯的整個犯罪過程分為 $N$ 個事件，並編號為 $1$ 到 $N$。然而因為現場附近沒有監視器，警方沒有強力的證據能夠推斷這些事件發生的順序以及確切時間。幸好在現場有許多目擊者，而且每位目擊者都看到了至少兩個事件，可以協助警方調查整個犯罪過程。
由於已經過了一段時間，這些目擊者沒辦法記得確切的事件發生順序，只能提供如「事件 $a$ 最晚發生在事件 $b$ 前 $d$ 秒」這樣的證詞（$d$ 有可能是負的，可以理解成「事件 $a$ 最晚發生在事件 $b$ 後 $-d$ 秒」）。另外，這些目擊者也不完全可信，因此有可能會發生不同目擊者的證詞彼此矛盾的情況。
為了協助警方調查，請你寫一個程式，根據這些目擊者的證詞輸出一組可能的事件發生時間，或判斷證詞是否有矛盾的情況，以方便警方重建犯罪過程，並過濾這些目擊者的證詞。
Input Format
第一行有兩個正整數 $N,M$，代表整個犯罪過程有 $N$ 個事件，並且目擊者總共提供了 $M$ 個證詞。
接下來有 $M$ 行，每行有三個整數 $a_i, b_i, d_i$，代表第 $i$ 個證詞是「事件 $a_i$ 最晚發生在事件 $b_i$ 前 $d_i$ 秒」。
對於所有測資，$2\leq N \leq 1000; M \leq 5\times 10^ 5; 1\leq a_i,b_i\leq N; a_i\neq b_i; -10\leq d_i\leq 10$。
Output Format
如果目擊者的證詞有任何矛盾的情況，請輸出一行 -1；否則請輸出 $N$ 行，第 $i$ 行有一個整數 $t_i$，代表第 $i$ 個事件發生在第 $t_i$ 秒是一組符合所有目擊者訊息的解。輸出的 $t_i$ 必須滿足 $|t_i| \leq 10^ 6$。
Sample Input 1
1 2 2
2 3 2
Sample Output 1
2
1000
Sample Input 2
1 2 1
2 1 1
Sample Output 2
Hints
Problem Source
改編自 NWERC 2011 pG
Problem Set by Yihda Yol
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~11 | 100 |