a308: Plan A Temporary Habitat
標籤 :
通過比率 : 14人/15人 ( 93% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-02-03 22:34

內容

五汗族是個神奇的民族,他們所生活的地區是由一些聚落與連接聚落的道路所組成,且可以以一張簡單圖表示在地圖上,其中每個聚落分別以$1\sim n$來編號,且每條道路上標有兩聚落間的距離(單位:公尺)。原本五汗族的人們近期定居在編號$s$的聚落,但由於現在發生了一些變故,他們打算遷移到聚落$t$,為了能評估他們遷移所需要的時間,請你幫他找出由$s$到$t$的最短路徑長度為何?

輸入說明

第一行輸入4個正整數$n,m,s,t (1\le n,m\le 200000 ; 1\le s,t\le n ; s\ne t)$分別代表聚落數量、道路數量、與題目所述的兩聚落編號。

接下來有$m$行每行3個正整數$u,v,d (1\le u,v\le n ; 1\le d\le 10^7)$代表聚落$u,v$之間有一條距離$d$且雙向皆可通行的道路。

保證$s$與$t$連通。

 

輸出說明

輸出一個正整數為題目所求的答案。

範例輸入
5 7 3 1
4 3 2
2 1 3
4 2 5
1 5 3
4 5 5
3 2 4
5 2 3
範例輸出
7
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (6%): 1.0s , <1K
公開 測資點#1 (6%): 1.0s , <1K
公開 測資點#2 (6%): 1.0s , <1M
公開 測資點#3 (6%): 1.0s , <1M
公開 測資點#4 (6%): 1.0s , <1M
公開 測資點#5 (6%): 1.0s , <10M
公開 測資點#6 (6%): 1.0s , <10M
公開 測資點#7 (6%): 1.0s , <10M
公開 測資點#8 (6%): 1.0s , <10M
公開 測資點#9 (6%): 1.0s , <10M
公開 測資點#10 (6%): 1.0s , <10M
公開 測資點#11 (6%): 1.0s , <10M
公開 測資點#12 (7%): 1.0s , <10M
公開 測資點#13 (7%): 1.0s , <10M
公開 測資點#14 (7%): 1.0s , <10M
公開 測資點#15 (7%): 1.0s , <10M
提示 :
標籤:
出處:
[管理者:
giver (垃圾)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」