1379 . 司令部的危機2
TopCoder
Tags
Description
司令部的電腦出大問題了！
由於電腦中毒，在一些重要場所的自動門壞掉了，像是：廁所。
等不及工程師把電腦修好，你現在很急，急的像熱鍋上的螞蟻
於是你翻越一本密集：魔女宅急便。故事敘述，是一個很宅的魔女，他急著找廁所想要方便一下。
書中給了絕對可以開門的大絕：只要跑遍每個廁所，那麼你到達的最後一個廁所，無論如何都會開門
另外他也有提到，一個廁所不能經過兩次，否則最後將無法開啟廁所的門
還有!!就是你覺得用盡一切力量只能再忍受d秒的時間，如過超越這個時間，你將會 ...
Input Format
包含多組測試資料。(測試資料不超過十組)
第一行為三個數字，n，m，d分別代表有幾個廁所，幾條連接廁所與廁所的通道，能夠忍住的時間是多少(秒)
(0≦n≦20，0≦m≦500，0≦d≦10000)
接著有m行，每行也是三個數字，st，ed，len，分別代道路兩端連結的廁所編號以及 你走這條通道會花費的時間(秒)
(0≦st，ed≦n-1，0≦c≦10000)
Output Format
如果可以在限制內達到廁所輸出OK
否則輸出...
Sample Input 1
6 10 8
0 1 3
0 2 3
0 5 2
1 2 1
1 3 2
1 4 2
1 5 4
2 3 5
3 4 9
4 5 1
4 4 6
0 1 1
0 3 4
1 2 2
2 3 3
0 1 3
0 2 3
0 5 2
1 2 1
1 3 2
1 4 2
1 5 4
2 3 5
3 4 9
4 5 1
4 4 6
0 1 1
0 3 4
1 2 2
2 3 3
Sample Output 1
...
OK
OK
Hints
宮崎駿對不起!! <(_ _)>
Problem Source
原TIOJ1379 / 快樂暑假營第二次練習比賽。
(Hamiltonian Cycle) Problem Setter：ggm
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 20 |
| 2 | 1 | 20 |
| 3 | 2 | 20 |
| 4 | 3 | 20 |
| 5 | 4 | 20 |