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
#include <cstdio>
#define MM 102
#define INF 8948309
int N,M,s,t,w;
int d[MM][MM];
int main(){
    for(int i=0;i<MM;i++)
        for(int j=0;j<MM;j++)
            d[i][j]=i==j?0:INF;
    scanf("%d %d",&N,&M);
    while(M--){
        scanf("%d %d %d",&s,&t,&w);
        d[s][t]=d[t][s]=d[t][s]>w?w:d[t][s];
    }
    for(int k=1;k<=N;k++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)
                if(d[i][j]>d[i][k]+d[k][j])
                    d[i][j]=d[i][k]+d[k][j];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)
            printf("%d ",d[i][j]);
        printf("\n");
    }
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX