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
#include <stdio.h>
#include <string.h>
#define MAXN 100
int main(void) {
    int map[MAXN + 1][MAXN + 1], n, m, from, to, length, i, j, k;
    scanf("%d%d", &n, &m);
    memset(map, -1, sizeof(map));
    for (i = 1; i <= n; ++i)
        map[i][i] = 0;
    while(m--) {
        scanf("%d%d%d", &from, &to, &length);
        if (map[from][to] == -1 || map[from][to] > length)
            map[from][to] = map[to][from] = length;
    }
    for (k = 1; k <= n; ++k)
        for (i = 1; i <= n; ++i)
            for (j = 1; j <= n; ++j)
                if (map[i][k] != -1 && map[k][j] != -1)
                    if (map[i][j] == -1 || map[i][j] > map[i][k] + map[k][j])
                        map[i][j] = map[i][k] + map[k][j];
    for (i = 1; i <= n; ++i)
        for (j = 1; j <= n; ++j)
            printf("%d%c", map[i][j], j == n ? '\n' : ' ');
    return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX