d335. 10009 - All Roads Lead Where?
Tags :
Accepted rate : 175人/183人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-09-06 20:06

Content

「條條大路通羅馬。」是一句古老的名言,但若這個假設成立,那就不難發展出一套找出任兩個城市之間一條路徑的演算法。

 

當你要從city A到city B時,你可以先從A到Rome,再從Rome到B,但這AB間可能存在一條更短的路徑。

 

對於Rome道路系統可以用一個簡單的結構描述:

從Rome開始有很多延伸出去的路通往相鄰的城市,從這些城市又有更多的路通往更遠的城市,以此類推……因此我們可以將城市和Rome按「等級」歸類,即等級i的城市只和等級i+1和等級i-1的城市相鄰(Rome則相當於等級0)。

 

系統內將不會出現環之類的路徑,任一個等級i的城市只能和一個等級i-1的城市相鄰,但可以和零個或多個等級i+1的城市相鄰,因此當我們要從一個等級i的城市走到Rome可以順著等級i-1的城市走。

 給定一連串的城市和道路,你的程式必須找出兩個城市之間的最短路徑(我們以拜訪的城市數量代替兩城市間的距離)。
Input

輸入的第一行為測試資料筆數,隨後接著空白的一列。

 

測資的第一行包含兩個以空白分隔的整數,第一個整數M表示系統中有幾條道路,第二個整數N表示你將要詢問兩個城市的最短路徑。

 

接下來的M行包含了一對由空白分隔的城市名稱,城市名稱包含一個或多個字母,第一個字母一定是大寫,任兩個城市名稱不會以相同字母開頭。

 

Rome這個名稱至少會在一組測資裡出現一次,而Rome被視為等級0的城市(等級最低的城市),該城市名稱間表示有一條道路相連,且保證第一個出現的城市的等級一定比第二個城市的等級低。沒有一個城市名稱對會重複出現兩次。

 

接下來的N行包含了兩個城市,且保證任兩個城市名稱一定在先前描述道路系統時出現過,則請輸出從第一個城市到第二個城市的最短路徑為何。

 任兩組測試資料間由一個空白行分格。 
Output

對於每對題目的詢問,請依序輸出位於該兩個城市最短路徑上的城市,輸出的城市名稱以第一個大寫字母作代表。

 

對於任兩組輸出間請輸出一個空白行。

 
Sample Input #1
1

7 3
Rome Turin
Turin Venice
Turin Genoa
Rome Pisa
Pisa Florence
Venice Athens
Turin Milan
Turin Pisa
Milan Florence
Athens Genoa
Sample Output #1
TRP
MTRPF
AVTG
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
樹的走訪
Tags:
出處:
UVa10009 [管理者: pcshic (PCSHIC) ]

Status Forum 排行

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