$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; }
댓글 없음 :
댓글 쓰기