TopCoder

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

User's AC Ratio

93.9% (108/115)

Submission's AC Ratio

38.9% (165/424)

Tags

Description

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

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

Input Format

第一行是兩個整數 $n,m (1 \leq n \leq 1000, 1 \leq m \leq n^{2})$。$n$ 代表有幾個點,$m$ 代表有幾個邊。

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

接著有 $m$ 行,每行皆有三個整數 $a_i, b_i, c_i (1 \leq a_i, b_i \leq n, 0 \leq c_i \leq 10^{6})$ 代表 $a_i$ 到 $b_i$ 有條方向未定的邊,路徑長為 $c_i$。

輸入包含多組測試資料。

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