TopCoder

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

12.5% (2/16)

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

Sample Output 1

...
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 65536 262144 1
1 4000 65536 262144 2
2 4000 65536 262144 3
3 4000 65536 262144 4
4 4000 65536 262144 5