Login with GitHub. Nope?
修正 C++ 的程式碼在使用一定量動態記憶體後會產生 RF 的問題 @ 2019/12/6 4:45pm NeoHOJ 強勢復活中 (Open beta)
Submit  Ranklist

Problem : 138 - 海綿寶寶之我要吃美味蟹堡(最短路)

Problem Statistics

Solved Member: 55  Submission: 301  User Tried: 56

Statement:


「喔,我好愛你,蟹堡王,
 美味蟹堡,鮮嫩多汁,油味讓我好興奮,
 價錢超貴,份量超小,牆上還粘著芥末醬。」──────蟹堡王之歌

蟹堡王位於比奇堡的市中心,大家都好喜歡吃蟹堡王的美味蟹堡。
今天派大星想要去吃蟹堡王的美味蟹堡,可是因為他太胖了,所以只要走路走太遠膝蓋就會受不了。
比奇堡有n個由道路連結而成的節點,並且有m條單向道路,這m條道路可能有不同的長度。
現在派大星在節點1,他想要選一條最短的路徑走到位於節點n的蟹堡王。
不過因為他能走的路徑長度有一定限制,請你告訴他最短的一條路徑長度是多少吧!
如果不存在這樣的路徑,請輸出-1。

Input:Output:

第一行有兩個數字n, m。(n ≦ 50000, m ≦ 300000)
接下來有m行,每一行有三個數字a, b, c (1 ≦ a,b ≦ n, 0 < c ≦10000),代表從節點a到節點b有一條長度為c的單向道路連接。
輸出一個數字,代表派大星要到蟹堡王的最短路徑。
若不存在最短路徑,請輸出-1。

Sample Input:Sample Output:

3 4
1 2 1
2 3 1
1 3 4
1 2 2
2

HINT:

我愛海綿寶寶>///<

Problem Setter

Testdata:

TestTimeMemoryScore
01000ms65536kb
1-11000ms65536kb10
1-21000ms65536kb
2-11000ms65536kb10
2-21000ms65536kb
3-11000ms65536kb10
3-21000ms65536kb
4-11000ms65536kb10
4-21000ms65536kb
5-11000ms65536kb10
5-21000ms65536kb
63000ms65536kb10
73000ms65536kb10
83000ms65536kb10
93000ms65536kb10
103000ms65536kb10