回分類題庫
d158: All Pairs Shortest Paths
出處:

Difficulity : 1
Accepted : 7 Times | Submit :220 Times | Clicks : 1658
Accepted : 4 Users | Submit : 13 Users | Accepted rate : 31%
Time Limit :5500 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2010-02-27 16:54

Content :

對一有向圖G = (V, E),和權重函數w : E -> Z而言,我們說一條路徑 p = <v0, v1, ..., vk>的權重,是(v0, v1)的權重 + (v1, v2)的權重 + ... + (vk-1, vk)的權重。在現實生活中我們可視權重為路徑長度,現給定一有向圖及權重函數,請計算任兩點之間的最短路徑。

Input :

測資為多筆,每一筆的第一行為一正整數n (1 ≤ n ≤ 1000),代表圖形的節點數。接下來的n行,每行各有n個數字。第i行的第j的數字代表著節點i到節點j的邊的權重(-1000 ≤ 權重 ≤ 1000),如果權重為0代表節點i到節點j沒有直接連接。 

Output :

針對每一筆測資,輸出n行,每行n個數字,第i行的第j個數字代表節點i到節點j的最短路徑的長度,節點i到節點i的最短路徑必為0。

Sample Input :

5
0 3 8 0 -4
0 0 0 1 7
0 4 0 0 0
2 0 -5 0 0
0 0 0 6 0
5
0 3 8 0 -4
0 0 0 1 7
0 4 0 0 0
2 0 -5 0 0
0 0 0 6 0

Sample Output :

0 1 -3 2 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0
0 1 -3 2 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0

Hint :

Floyd-Warshall algorithm

Author :

(管理員:yuhanlyu)

  Solve it!   Status Forum (2)

C++
C
JAVA
50133. zeus ( 1.1 s , 2272KB)
18373. nipa (793 ms , 2134KB)
18499. Tc (814 ms , 1886KB)
18375. yuhanlyu (815 ms , 1893KB)
18374. nipa (823 ms , 4161KB)
18377. yuhanlyu (836 ms , 1887KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡