g422: PD.紅血球的快遞任務
Tags :
Accepted rate : 16人/20人 ( 80% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-10-24 14:52

Content

身為每天辛苦工作的紅血球,今天你與一如往常地要將氧氣送給身體裡各個需要的細胞。

然而,剛從心臟出發沒多久,你就不幸的迷路了。此時你所能依靠的,只剩下隨身攜帶的地圖。

地圖上標示著$n$個器官,包括你的起點心臟($0$號)及其他各個器官($1 \sim n-1$號),而你手中氧氣的客戶細胞則住在$b$號器官。

地圖上也標示了$m$條血管,以及每條血管的長度、起點及終點。這些血管都是可以雙向通行的。

請問你可以憑藉這張地圖,找出最快送達氧氣的路徑嗎?

 

Input

第一行輸入$n,m,b$,表共$n$個器官,$m$條連通血管,求從心臟($0$號器官)到目標細胞的住所($b$號器官)的最短距離
接下來一共$m$行,每行輸入三個數字,$a,b,w$
表示$a,b$器官之間有一條血管,長度為$w$

保證所有測資符合

$1\le n,m\le 10^5,1\le b \le n-1$

$0\le a,b\le n-1,1\le w\le10^4$

Output

輸出一個數字表點$0$到點$b$的最短距離

Sample Input #1
3 3 2
0 1 2
0 2 4
1 2 5
Sample Output #1
4
測資資訊:
記憶體限制: 128 MB
不公開 測資點#0 (25%): 2.0s , <1M
不公開 測資點#1 (25%): 2.0s , <1M
不公開 測資點#2 (25%): 2.0s , <10M
不公開 測資點#3 (25%): 2.0s , <10M
Hint :

 

從0到2有兩條路
(0-1-2)距離7
(0-2) 距離4
輸出4

 

保證圖連通
不會有重邊/自環

subtask1 (49%) : $w=1$

subtask2 (41%) : $w=0 \lor 1$

subtask3 (10%) : $1\le w\le10^4$

題目-雞蛋

p.s 窩不會出題QAQ

Tags:
出處:
[管理者:
kaihsinchen2 (Kai-Hsin Chen 2)
]


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