c152. E. 搭公車 - 大魏線上解題系統

Content

小明每天都需要搭公車上學，由於不一定有直達車讓他到學校，因此他需要在許多公車中繼站轉乘。他的家位於郊區，而學校則在繁忙的市中心。由於早晨的交通總讓他心急如焚，小明決定找出一條轉乘次數最少的路線，以節省通勤時間。

整個城市的公車站（可能是中繼站，也可能是只有一條邊與其相鄰的端點）可以用一張無向圖表示，圖中的每個節點代表一個公車站，每條邊代表一條直達路線。其中你知道共有 $N$ 個公車站（編號為 $1$ 到 $N$）以及 $M$ 條直達路線，也知道小明家一定位於編號 $1$ 的節點，且學校也一定位於編號 $N$ 的節點，請幫助小明計算出從家到學校最少需要搭多少班公車，也就是編號 $1$ 節點到編號 $N$ 節點所能經過的最小邊數。

舉例來說，若有 $5$ 個公車站及六條直達路線 $(1,2)$、$(1,3)$、$(2,4)$、$(2,5)$、$(3,5)$、$(4,5)$ ，分布如下圖：

可以發現從編號 $1$ 的節點到編號 $5$ 的節點所經過的最小可能邊數為 $2$，為經過編號 $3$ 的節點到達的路徑。

Input

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$u_3$ $v_3$
$\dots$
$u_M$ $v_M$

$2\le N\le 100$
$1\le M\le \frac{N(N-1)}{2}$
$1\le u_i,v_i\le N,u_i\neq v_i$
每筆 $u_i$ $v_i$ 表示節點 $u_i$ 與 $v_i$ 有直達路線
保證編號 $1$ 的節點與編號 $N$ 的節點相連

Output

$ans$

輸出編號 $1$ 節點到編號 $N$ 節點所能經過的最小邊數。

Sample Input #1

Sample Output #1

Sample Input #2

Sample Output #2

Sample Input #3

Sample Output #3

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1K
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <1K
公開測資點#7 (5%): 1.0s , <1K
公開測資點#8 (5%): 1.0s , <1K
公開測資點#9 (5%): 1.0s , <1K
公開測資點#10 (5%): 1.0s , <1K
公開測資點#11 (5%): 1.0s , <1K
公開測資點#12 (5%): 1.0s , <1K
公開測資點#13 (5%): 1.0s , <1K
公開測資點#14 (5%): 1.0s , <1K
公開測資點#15 (5%): 1.0s , <1K
公開測資點#16 (5%): 1.0s , <1K
公開測資點#17 (5%): 1.0s , <1K
公開測資點#18 (5%): 1.0s , <1K
公開測資點#19 (5%): 1.0s , <1K

Hint ：

Tags:

BFS 圖論

出處:

114學年校內能競選拔 [管理者： jackhuang(fijjj) ]

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