Tube's World

Q: http://uva.onlinejudge.org/external/106/10682.html

 又一網路上無題解的題目

事後才發現過的不到150個@@

寫完之後覺得這題其實沒有很難

就是紀錄經過哪些城市時比較tricky而已

解法為BFS

從起點開始找附近有哪些城市是:

1.有道路連接,且車子不必減速的城市

2.注意道路是雙向的,如果仔細推敲就可以知道說一條道路最多只能經過一次,不可能經過2次

利用上述兩點來寫BFS, 判斷一個城市是否可以丟進queue裡面

至於紀錄有經過哪些城市時

要記得紀錄上一個和上上一個城市

要不然上上一個城市有可能會被覆蓋掉(卡這邊卡超久= =)

至於這題為什麼可以用BFS來求最短路徑應該還蠻好理解的吧

這題城市之間的距離並沒有長短的分別,大家彼此之間的距離都一樣

所以在你附近最先找到的城市一定就是離你最近的城市

因此只要一發現有一條路可以通往終點,那條路一定就是最短路徑

最後注意如果存在多條路徑,要輸出有"最先出現的城市名稱"的那條

ex.

4

A B 12

A C 15

C D 20

B D 20

A D

答案可以是 A-->B-->D 或是 A-->C-->D

此時要輸出 A-->B-->D這條,因為在測資中B城市比C城市先出現(很多人的WA都卡在這)

還有就是會出現亂入的城市,此時要直接輸出No valid route (因為這個吞了WA = =)

少數有進前20名的題目@w@

不過也是因為解題人數少吧ˊ_>ˋ

破200題了, 繼續加油!!