a210:
星際快遞
內容
在科技發達的未來，人類掌握了「超空間航道」技術，擺脫了光速的限制，進入了繁榮的星際時代。
戴克斯特拉(Dijkstra)是在泰拉公司上班的一名員工，他每天的工作就是將公司一份貴重的貨物送達目的地。
今天是個特別的日子：【大小姐想讓人告白】劇場版在今天要撥出了。為了不錯過時間，戴克斯特拉希望能在最短的時間內將今天的貨物送到站。
你能幫戴克斯特拉算算他送到貨最少需要多少時間嗎？
注意：由於空間扭曲等等複雜的因素，兩顆星星之間可能沒有架設航道，
也有可能直接搭乘從A星到C星的航班所花費的時間，不一定比先從A星搭到B星，再從B星搭到C星所花的時間短。
輸入說明
輸入第一行為四個整數 N、M、S、E ，代表這片星域有編號 0~N-1 的共 N 顆星星，總共有 M 個連接兩顆不同星星的超空間航道，並且戴克斯特拉將把貨物從 S 星送到 E 星。
接下來的 M 行，每一行都有三個數字 X、Y、T ，代表X星與Y星之間有超空間航道，而從X星抵達Y星(或從Y星抵達X星)所花的時間為 T 。
兩顆星星間最多只有一個超空間航道。
2 ≤ N，M ≤ 3×105。
0 ≤ S，E ≤ N-1 且 S ≠ E。
0 ≤ X，Y ≤ N-1 且 X ≠ Y。
1 ≤ T ≤ 105。
輸出說明
輸出單個整數，代表從 S 星到 E 星所需花費的最短時間。
如果不能從從 S 星抵達 E 星，輸出-1。
範例輸入
#1
5 5 0 4 0 1 3 1 2 4 2 4 11 2 3 1 3 4 6
範例輸出
#1
14
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1M
不公開 測資點#2 (20%): 1.0s , <1M
不公開 測資點#3 (20%): 1.0s , <1M
不公開 測資點#4 (20%): 1.0s , <1M
不公開 測資點#5 (20%): 1.0s , <1M
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1M
不公開 測資點#2 (20%): 1.0s , <1M
不公開 測資點#3 (20%): 1.0s , <1M
不公開 測資點#4 (20%): 1.0s , <1M
不公開 測資點#5 (20%): 1.0s , <1M
提示 ：
範例測資中，花費最短時間的路徑為0 → 1 → 2 → 3 → 4，時間為3 + 4 + 1 + 6 = 14。
出處:
經典問題
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||