五汗族是個神奇的民族,他們所生活的地區是由一些聚落與連接聚落的道路所組成,且可以以一張簡單圖表示在地圖上,其中每個聚落分別以$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
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |