10117. Fast Dynamic Programming Computing II (OpenMP)

I'm a slow walker, but I never walk backwards.

題目描述

給定一張圖 $G=(V,E)$,根據 Floyd-Warshall Algorithm 計算 All-Pair Shortest-Path 的所有結果。計算流程可參考以下程式。

sequence.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include <stdlib.h>
#define INF 0x3f3f3f3f
#define MAXN 1024
int g[MAXN][MAXN];
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &g[i][j]);
                if (g[i][j] == 0)
                    g[i][j] = INF;
            }
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    int cost = g[i][k] + g[k][j];
                    if (g[i][j] > cost)
                        g[i][j] = cost;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                printf("%d%c", g[i][j] == INF ? 0 : g[i][j], " \n"[j==n-1]);
            }
        }
    }
    return 0;
}

輸入格式

有多組測資,每組第一行會有一個整數 $N$ 表示有 $N$ 個節點,接下來會有 $N$ 行,在第 $i$ 行上會有 $N$ 個數,第 $i$ 行上的第 $j$ 個數表示節點 $i$ 到節點 $j$ 的花費 $w_{ij}$,以 $w_{ij} = 0$ 表示兩節點之間沒有直接的邊。

  • $1 \le N \le 1000$
  • $1 \le w_{ij} \le 10000$

輸出格式

對於每組測資,輸出 $N$ 行 $N$ 個整數,印出節點到節點的最短路徑,請參考範例輸入輸出。

範例輸入

4
0 5 0 10
0 0 3 0
0 0 0 1
0 0 0 0

範例輸出

0 5 8 9
0 0 3 4
0 0 0 1
0 0 0 0

Discussion