回分類題庫
d062: 5.最短路徑
關鍵字: 101年彰雲嘉區複賽

測資點 : 3 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 54 Times / 37 Users | Submit : 280 Times / 47 Users | Accepted rate : 79%
題目加入時間 : 2013-10-31 10:33

Content: 简体中文

假設某工廠的無人自走車行走路徑如下圖,其中f、g兩點與k、o兩點間並無直接路徑相連,自走車負責循線載送生產原料或半成品至各點。請設計一程式可計算自走車必須行走的最短路徑長度。例如從a點出發至f點,則最短路徑長度為2,又例如從a點出發,須拜訪g、p、f、n (可依任意順序),則最短路徑長度為9 (a→b→f→j→n→o→p→l→k→g)。若某點在需拜訪的點串列中重複出現,則只需拜訪一次即可,例如從d點出發,須拜訪f、b、k、f、p,則最短路徑長度為7 (d→c→b→f→j→k→l→p)。

 

Input:

測試資料第一行有一正整數N表示測試資料組數,接下來有N行資料,每一行資料內容如下:
第一個英文字母代表出發點,接下來的字母代表必須拜訪的點(可依任意順序),字母與字母間以一個空白做間隔。

Output:

每一組測試資料須輸出一個數字代表此次行走的最短路徑長度,輸出下一組最短路徑長度時須跳行。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
a f
a g p f n
d f b k f p

Sample Output :

2
9
7

Hint :

Author :

101年彰雲嘉區複賽 (管理員:sagit)

  Solve it!   Status Forum