ssl02模式，城市交通_ssl1636_floyd

Description

　　有n個城市，編號1~n，有些城市之間有路相連，有些則沒有，有路則當然有一個距離。現在規定只能從編號小的城市到編號大的城市，問你從編號為1的城市到編號為n的城市之間的最短距離是多少？

Input

先輸入一個n，表示城市數，n小于100。?
下面的n行是一個n*n的鄰接矩陣map[i,j],其中map[i,j]=0表示城市i和城市j之間沒有路相連，否則為兩者之間的距離。

ssl02模式。

Output

輸出格式：一個數，表示最少要多少時間。?
輸入數據保證可以從城市1飛到城市n。?

Sample Input

11

0 5 3 0 0 0 0 0 0 0 0

5 0 0 1 6 3 0 0 0 0 0

3 0 0 0 8 0 4 0 0 0 0

0 1 0 0 0 0 0 5 6 0 0

0 6 8 0 0 0 0 5 0 0 0

0 3 0 0 0 0 0 0 0 8 0

0 0 4 0 0 0 0 0 0 3 0

0 0 0 5 5 0 0 0 0 0 3

0 0 0 6 0 0 0 0 0 0 4

0 0 0 0 0 8 3 0 0 0 3

0 0 0 0 0 0 0 3 4 3 0

Sample Output

13

思路：

因為是最短路所以想到最短路，n不大就用floyd。對于給定的鄰接矩陣作floyd然后輸出f[1,n]。

?

源代碼/pas:

?

varn,i,j,k:longint;f:array[1..500,1..500]of longint;
beginreadln(n);for i:=1 to n dofor j:=1 to n dobeginread(f[i,j]);if (f[i,j]=0)or(j<=i) thenf[i,j]:=maxlongint div 2;end;for k:=1 to n dofor i:=1 to n dofor j:=1 to n doif (k<>i)and(k<>j)and(i<>j)and(f[i,k]+f[k,j]<f[i,j]) thenf[i,j]:=f[i,k]+f[k,j];writeln(f[1,n]);
end.