[UVA] 157 Route finding

思路： 利用Dijkstra求起點到終點的最短路徑。同一條線上相鄰的車站距離為1，不同線相交轉車的距離為3，接著求最短路徑。parse input時同時建立graph。

Dijkstra在C++的實作要點在於，relax distance需要一個支援update value (decrease key) 的 min heap。常見作法有二，一是用priority_queue，每次relax 時塞一個新的(node, relaxed_distance)進heap。由於relax後的同node一定有比較小的distance，所以一定會在heap的較上方。舊的distance就會被擠到下面，而在pop時被忽略。

另一個作法是用set 配合pair (node, distance)。每當要update node時，先把(node, old_distance)從set中移除 ，再新增一個pair (node, new_distance)。也就是用 delete/insert來達到 decrease key的目的。Top coder有非常完整的解說。

這一題有一個蠻有趣的陷阱，害我吃了一個WA。這是從forum上copy下來的範例:

5 
A:ab=Bbcdefghijk 
B:abc=Ajdef=Cb 
C:ab 
D:cd=Eg 
E:fg=Bf 
AaAk 
AcAk 
AbBb 
BaDd 
# 

The correct output is: 
9: Aab=Bbc=Ajk 
8: Acdefghijk 
3: Ab=Bb 
8: Babcdef=Dd 

WA output:
9: Aab=Bbc=Ajk 
8: Acdefghijk 
3: Ab=Bb 
11: Babcdef=Eg=Dd
陷阱在於，可能有複數個stations同為一個connection set，但是input沒有窮舉set中的任兩兩。如上題中，connection should be:
  Bf=Cb=Dd=Eg
但是題目只列出部份:
  Bf=Cb  Bf=Eg  Eg=Dd
也就是 Cb=Dd (以及 Cb=Eg, Bf=Dd)是需要程式自己推導出的。這種集合的驗證蠻麻煩的，所以我用了一些trick: 當'x=y'出現，可以知道x車站與y車站相連。製造出一個虛擬車站 C1，
且有邊： cost(x, C1) = cost(y, C1) = 3, cost(C1, x) = cost(C1, y) = 0 這樣 x 到 y, y 到x 的cost都是3。
接著當 y=z出現時，由於 y 已經連到 C1了，所以可以直接讓z 也連到 C1。如果z 之前連到另一個虛擬車站C2，那我們可以把C1跟C2連起來: cost(C1, C2) = cost(C2, C1) = 0，於是z 到 x 也是 cost = 3了。