內容
身為每天辛苦工作的紅血球，今天你與一如往常地要將氧氣送給身體裡各個需要的細胞。
然而，剛從心臟出發沒多久，你就不幸的迷路了。此時你所能依靠的，只剩下隨身攜帶的地圖。
地圖上標示著$n$個器官，包括你的起點心臟($0$號)及其他各個器官($1 \sim n-1$號)，而你手中氧氣的客戶細胞則住在$b$號器官。
地圖上也標示了$m$條血管，以及每條血管的長度、起點及終點。這些血管都是可以雙向通行的。
請問你可以憑藉這張地圖，找出最快送達氧氣的路徑嗎?
輸入說明
第一行輸入$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$
輸出說明
輸出一個數字表點$0$到點$b$的最短距離
範例輸入
#1
3 3 2 0 1 2 0 2 4 1 2 5
範例輸出
#1
4
測資資訊：
記憶體限制：
128
MB
不公開 測資點#0 (25%): 2.0s , <1M
不公開 測資點#1 (25%): 2.0s , <1M
不公開 測資點#2 (25%): 2.0s , <10M
不公開 測資點#3 (25%): 2.0s , <10M
不公開 測資點#0 (25%): 2.0s , <1M
不公開 測資點#1 (25%): 2.0s , <1M
不公開 測資點#2 (25%): 2.0s , <10M
不公開 測資點#3 (25%): 2.0s , <10M
提示 ：
從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
標籤:
出處:
[管理者：
kaihsinchen2
(Kai-Hsin Chen 2)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 41886 |
|
g422 | 43 | 2024-09-07 16:19 |