1290 . F.不定向邊

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

93.9% (108/115)

Submission's AC Ratio

38.9% (165/424)

Tags

KSHSVC 2008-KSHSVC

Description

給一個圖，單向邊，邊有cost，一開始邊是未決定方向的，你可以對任意條邊決定一個方向。

接著，問起點到終點最短路徑。

Input Format

第一行是兩個整數 n,m(1≤n≤1000,1≤m≤n2)。n 代表有幾個點，m 代表有幾個邊。

第二行是兩個整數 st,ed(1≤st,ed≤n)。st 代表起點，ed 代表終點。

接著有 m 行，每行皆有三個整數 ai,bi,ci(1≤ai,bi≤n,0≤ci≤106) 代表 ai 到 bi 有條方向未定的邊，路徑長為 ci。

輸入包含多組測試資料。

Output Format

輸出一個貌似答案的整數。

如果到不了的話輸出 "He is very hot"（不含雙引號）

Sample Input 1

5 4
5 1
4 1 6
3 3 1
4 5 2
2 5 4

5 1
3 3
2 4 5

Sample Output 1

8
0

Hints

2008/05/11 輸入範圍修正，0≤ci≤106，感謝newmoon，Darkseer。被陰到的請見諒<(_ _)>
2008/05/15 Output的敘述修正：正整數→整數。感謝shik

Problem Source

原TIOJ1290 / 雄中公假社'08 入退社考。Problem Setter：ggm。

Subtasks

No. Testdata Range Score
1 0 33
2 1 33
3 2 34

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
Submit
Back to Top