|
執行檔 |
message.exe |
輸入檔 |
message.in |
|
執行時間限制 |
30秒 |
輸出檔 |
message.out |
因應時代的進步，阿米巴星球的軍事大樓開始使用網路，來連接辦公室中的每一台電腦。最近他們開始為新架設好的網路系統作一些測試。
然而，測試的結果並不順利。因為兩兩相連的電腦處理速度、傳輸材質、以及傳輸距離不盡相同，有些電腦之間的傳輸速度很快，但也會有兩台電腦之間傳輸速度很慢的情況。軍事大樓最需要的，就是訊息廣播的功能，希望能在最快的時間內，讓所有的電腦都得知某項訊息(例如：有敵國向他們宣戰)，因此這套系統設計成每台電腦可以同時開始向其他n-1台廣播訊息。可是在一開始的設計中，他們忽略了兩兩電腦間傳輸速度不盡相同的問題，因此如果電腦A到電腦B的直接傳訊非常慢，由A發出的廣播，傳輸效率會很差。。
後來，他們想到一個新的主意：為了減小訊息傳遞所需的時間，所以訊息有些會用轉送的方式來傳遞，例如說：A到B的訊息可能可以走A到C、C再轉送給B的路徑，而可能可以達到比較好的傳輸效率。
請寫出一個程式協助阿米巴國防部測試這套系統，找出廣播一個訊息所需的最小時間。
輸入檔定義了多組各自獨立的測試資料，一組接著一組，每一組的內容如下所述：
第一行為所有電腦的數目n，其中1<=n<=100。
接著為一個表示連接關係的n x n矩陣A。矩陣的元素是一個正整數或是字元x。A(i,j)表示由電腦i直接送一個訊息到電腦j所花的時間。若A(i,j)為x的話，表示電腦i無法把訊息直接送到電腦j。
當然，一台電腦不需要花任何時間就可以送訊息給自己，所以對任一電腦i來說，A(i,i)=0。另外，你可以假定網路是沒有方向性的（在兩電腦間傳訊息所需的花費和方向無關，都是相同的），所以對任兩台電腦i,j來說，A(i,j)=A(j,i)。
因此，題目的輸入將只會包含矩陣A的下三角形部份（不包含對角線）。也就是說，第二行的只會有一個元素A(2,1)。第三行會有兩個元素，分別是A(3,1)和A(3,2)。
當讀到一組測試資料的第一行為0時，代表輸入檔的檔尾。
對每一組測試資料，輸出從第一台電腦廣播一個訊息到其它所有電腦所需的最短傳訊時間，一組一行。
5
50
30 5
100 20 50
10 x x 10
4
11
x 20
2 x 13
0
35
15