페이지

11404번: 플로이드

https://www.acmicpc.net/problem/11404


$O(n^3)$


#include<cstdio>
int n, m, c[101][101];
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (i - j)c[i][j] = 1e9;
    for (int i = 0, x, y, z; i < m; i++) scanf("%d %d %d", &x, &y, &z), c[x][y] = c[x][y]<z ? c[x][y] : z;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++)
        if (c[j][i] + c[i][k] < c[j][k]) c[j][k] = c[j][i] + c[i][k];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) printf("%d ", c[i][j] == 1e9 ? 0 : c[i][j]);
        puts("");
    }
    return 0;
}

댓글 없음 :

댓글 쓰기