回『AP325題庫』
e118: P-7-9. 最短路徑 (*)
Tags : Dijkstra
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式：
Tolerant

最近更新 : 2024-03-04 11:54

Content

輸入一個無向圖 G=(V,E,w)，其中點以 0~n-1 編號，而邊的權重是非負整數。計算 0 號點到其他點的最短路徑長度。兩點之間可能有多個邊。

Time limit: 1 秒

Input

第一行是兩個正整數 n 與 m，代表點數與邊數，接下來有 m 行，每行三個整數 u, v, w 代表一條無向邊(u,v)的長度是 w。n 不超過 1e4，m 不超過 1e5, w 是不超過 1e4 的非負整數。

Output

第一行輸出 0 到各點之最短路徑長度中的最大值，也就是在可以到達的點中，最短距離最大的是多少，第二行輸出有多少點無法從抵達。

Sample Input 
範例一：
7 6
0 2 3
0 1 1
2 3 4
1 4 0
3 4 2
5 4 3

範例二：
3 3
2 1 5
1 0 0
0 1 1
Sample Output 
範例一：
4
1

範例二：
5
0
測資資訊：
記憶體限制： 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
Hint ：

(範例測資中前兩筆的 n 不超過 500。)

Tags:
Dijkstra
出處:
AP325 [管理者：
mcjksieu005 (mcjksieu005)
]

Status Forum 排行

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