2013年8月13日 星期二

1247 - Interstar Transport

到了西元 2100 年,對於銀河系上的太空旅行已經實現了,星際旅行社打算規劃星球旅行,將兩個最受歡迎的星球設計路線,這路線的花費使用 Galaro 為貨幣單位,並且也出了許多不同語言版本,然而並不是任兩個星球都有被規劃路線,兩個星球間的旅行被限制於太空旅行清單中。

幫助旅客規劃他們的行程,星際旅行社想要提供一款行動 App 找到最佳旅行選擇,最加取決於兩個星球間的旅程花費, 給定起點與終點星球,找到一條路徑有最少花費,並且輸出路程中的每一個星球,如果有同一條路具有相同花費時,則找中間經過最少個星球為最佳路徑。每組測資只會存在一組最佳路徑。

條件限制

  1. 星球個數 s (1 <= s <= 26),且每個星球使用大寫英文字母表示 'A', 'B', 'C', ..., 'Z'。
  2. 星球間,最多存在 200 條可進行太空旅行的直通道路。
  3. 每條路線的花費都是一個正整數小於等於 100。
Input

輸入第一行會有兩個整數 s, p
接下來會有 p 行,每行上有兩個字元 ei , ej 以及一個整數 dij
表示 ei , e間可以進行太空旅行,且花費為 dij
緊接著會有一個整數 n (1 <= n <= 20),表示有多少組詢問,
接下來會有 n 行,每行上有兩個字元 ek , em,表示要求這兩個星球的最少花費路徑。

Output

對於每組詢問輸出一行,每個星球編號間以空白隔開,順序為從起點到終點從左至右輸出。

Sample Input

5 7 
A B 1
B C 2
C D 3
D E 2
E A 1
A D 3
A C 4
3 
B D 
A D 
E C
Sample Output
B A D 
A D 
E A B C