g422. PD.紅血球的快遞任務 - 高中生程式解題系統

內容

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

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

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

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

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

輸入說明

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

保證所有測資符合

$1 \leq n, m \leq 10^{5} ， 1 \leq b \leq n - 1$

$0 \leq a, b \leq n - 1 ， 1 \leq w \leq 10^{4}$

輸出說明

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

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 128 MB
不公開測資點#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 \leq w \leq 10^{4}$

題目-雞蛋

p.s 窩不會出題QAQ

標籤:

出處:

[管理者： kaihsinchen2 (Kai-Hsin Chen 2) ]

編號	身分	題目	主題	人氣	發表日期
41886	enhanwen8@gm ... (會寫程式的羊)	g422	Dijkstra’s Shortest Path Algorithm	117	2024-09-07 16:19