1719 測資加強 已 rejudge
1380 . 司令部的危機3
TopCoder
Tags
Description
司令部的電腦出大問題了！
由於電腦中毒，在一些重要檔案壞掉了，像是：H-game (Heuristic Gamer)。
等不及工程師把電腦修好，你現在很火，火的像熱名義老爸一樣火
於是你打開H-gameboy：這是由日本任天堂在1989年推出的掌上型遊戲機。之後新版內建Heuristic功能，於是稱之為H-gameboy
遊戲機的說明書給了可以絕對破解的密招：只要從電腦傳入H-game進遊戲機，那麼在你所傳的最後一個遊戲，無論如何都可以玩
另外你沒料到這天會發生，竟然將H-game分散放在司令部的電腦上!!
除此之外還是依循古老的原則，遊戲不能載入兩次以上，否則遊戲裡全部都是男性腳色。注意!!你可以經過電腦旁但是不載入遊戲
還有!!就是你覺得用盡一切力量只能再忍受d秒的時間不玩H-game，如過超越這個時間，你將會 ...
Input Format
包含多組測試資料。(測試資料不超過十組)
第一行為三個數字，n，m，d分別代表有幾個電腦，幾條電腦與電腦相連的通道，忍受的限制是多少(秒)
(0≦n≦20，0≦m≦500，0≦d≦10000)
接著有m行，每行也是三個數字，st，ed，len，分別代表邊兩端連結的電腦編號以及你在這通道移動所花的時間(秒)
(0≦st，ed≦n-1，0≦len≦10000)
Output Format
如果可以在限制內達到載入所有H-game輸出OK
否則輸出...
Sample Input 1
6 10 10
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
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
Sample Output 1
OK
Hints
任天堂社對不起<(_ _)>
※2008/07/17 題目敘述修正 by hallogameboy，感謝 ck961073。
Problem Source
原TIOJ1380 / 快樂暑假營第二次練習比賽。
(Adapt from：Hamiltonian Cycle) Problem Setter：ggm
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 25 |
| 2 | 1 | 25 |
| 3 | 2 | 25 |
| 4 | 3 | 25 |