[Java] UVa 10009 All Roads Lead Where

題目連結

題意:
有若干城市，城市之間可能存在連線
每組測資先給定m，n
代表有 m 組程式間的連線
接著問 n 組，從某地到另一地可能的最短路徑

針對n行問題，每行輸出最短路徑的每個城市第一個字母

例如:
3 1
Aa Bb
Aa Cc
Cc Dd
Aa Dd
如上，m = 3，n = 1
Aa和Bb，Aa和Cc，還有Cc和Dd之間有連線
然後問Aa到Dd可以怎麼走

最短路徑為 Aa-Cc-Dd，輸出ACD

解法:
先透過HashMap建立連線
Key - Value 代表可以從城市 Key 到城市 Value

因為連線是雙向的
所以當input為A B時
要分別以A為Key加B Value，以B為Key加A Value

此外，因為一個城市可能可以同時連到多個其他城市
Value可以用ArrayList<> (等於一個key對應多個Value)

然後，實作上可以用BFS
先建立另一個HashMap(prev) 紀錄路徑
也就是以S為起點時，有沒有其他城市(Value)可以走到特定城市(Key)
所以一開始會輸入 prev.put(S, null); //S是起點

每次讀取S和D (出發和目的地)
先讀S，判斷可以走到哪些城市(也就是BFS的第一層search)
若城市的prev不存在(表示BFS還沒掃過)，就紀錄到prev

當掃到D，就透過prev回朔到S
可以建立一個反轉的字串，最後輸出即可

程式(Java):