TopCoder

Thumb output jddoia
$\huge 南ことり$
今天也要輸贏!?

User's AC Ratio

95.3% (41/43)

Submission's AC Ratio

42.1% (69/164)

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

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

8
0

Hints

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

Problem Source

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

Subtasks

For Testdata: 0 ~ 0, Score: 33
For Testdata: 1 ~ 1, Score: 33
For Testdata: 2 ~ 2, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144