e014. 最短路徑-1 - 花中程式設計挑戰系統

Content

給定一張有向圖，請求出節點0到各節點的最短距離，若無法到達該節點請輸出-1。

Input

第一行有兩正整數n,m以空白隔開，n代表有向圖的節點數、m代表有向圖的邊數
接下來有m行，每行含三整數u,v,w，整數間以空白隔開，代表點u有一條通往點v且權重為w的邊

$n\le 10^5 , m\le 10^6$

$u\neq v,0\le u<n,0\le v<n,0<w\le 10^9$

不會有重邊、自環的情形

Output

請輸出n個正整數$a_0\ a_1\ ...\ a_{n-1}$在同一行，以空白隔開，$a_i$代表點0到點i的最短距離

Sample Input

Sample Output

0 7 5 5

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (25%): 1.0s , <1K
公開測資點#1 (25%): 1.0s , <1M
公開測資點#2 (25%): 2.0s , <50M
公開測資點#3 (25%): 1.0s , <1K

Hint ：

Dijkstra 演算法練習

Tags:

出處:

[管理者：

s810368 (test)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」