演算法 Floyd-Warshall algorithm

 avatar
user_6817964
c_cpp
a year ago
1.2 kB
1
Indexable
Never
int main()
{
    int n, m, i[201], j[201], w[201];
    scanf("%d%d", &n, &m);
    for (int k = 1; k <= m; k++) {
        scanf("%d%d%d", &i[k], &j[k], &w[k]);
    }

    int d[51][51] = {0};
    for (int r = 1; r <= n; r++) {
        for (int c = 1; c <= n; c++) {
            if (r == c) {
                d[r][c] = 0;
            }
            else {
                d[r][c] = 99999;
            }
        }
    }
    for (int k = 1; k <= m; k++) {
        d[i[k]][j[k]] = w[k];
    }

    for (int k = 1; k <= n; k++) {
        for (int r = 1; r <= n; r++) {
            for (int c = 1; c <= n; c++) {
                if (d[r][c] > (d[r][k] + d[k][c])) {
                    d[r][c] = d[r][k] + d[k][c];
                }
            }
        }
    }

    for (int r = 1; r <= n; r++) {
        if (d[r][1] == 99999) {
            printf("N");
        }
        else {
            printf("%d", d[r][1]);
        }
        for (int c = 2; c <= n; c++) {
            if (d[r][c] == 99999) {
                printf(" N");
            }
            else {
                printf(" %d", d[r][c]);
            }
        }
        printf("\n");
    }
}