c727: 教室在哪裡
Tags :
Accepted rate : 3人/9人 ( 33% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-08-06 14:50

Content

教室在哪裡

小華走進了學校而且快要遲到時,請幫他找出最快可以走到教室的方法。
學校的結構可以類比成N個點,教室間透過一些雙向道路連接起來。每一條路,只需花一秒就能從一端到達另一端。
當小華站在校門口1號點上,希望能從1號點用最少的步數走到N號點。
他手上有一張地圖,上面寫了M組關於地圖的資訊。每i組包含兩個數字(ai , bi),代表
著ai號點和bi號點之間,沒有道路相通,也就是說除了地圖上的M組關係之外,任兩個點都有路可以連接!
請問小華幾步能到達教室呢?

由於本題輸入數字龐大,使用 C++ cin, cout的同學請在主程式裡加入一行
cin.tie(0) , cout.sync_with_stdio(0);
再進行輸入輸出。

 

測資範圍
所有的N的總和 < 1000000,所有的M的總和 < 3000000

子任務:
10% : M 皆 <= n - 1
30% : N 的總和皆 <= 5000
30% : N 的總和皆 <= 100000
30% : 無特別限制

 

Input

多筆輸入
每一筆的第一行有兩個數字 N, M, 代表有N個點和M個關於地圖的資訊

Output

對於每一筆側資 請輸出一個數字代表從 1 走到 N 的秒數,若你根本沒有辦法到達教室 ,請輸出-1

Sample Input
3 3
1 2
2 3
3 1
5 2
1 5
2 4

Sample Output
-1
2
測資資訊:
記憶體限制: 128 MB
不公開 測資點#0 (10%): 0.6s , <10M
不公開 測資點#1 (30%): 0.8s , <50M
不公開 測資點#2 (30%): 0.8s , <50M
不公開 測資點#3 (15%): 1.5s , <50M
不公開 測資點#4 (15%): 1.5s , <50M
Hint :
Tags:
出處:
[管理者:
boook (boook)
]


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