d282. 11015 - 05-2 Rendezvous -- UVa11015 | From: [118.163.88.50] | 發表日期 : 2014-08-11 18:49

#include <stdio.h>

int main(void)

{

int a, b, c, n, m, mid[n][n], dist[n][n];

while ( scanf("%d%d" ,&n ,&m) == 2 ){

for (int i=0; i<n; i++){

for (int j=0; j<n; j++){

mid[i][j] = -1;

dist[i][j] = 1000000000;

}

}

for (int i=0; i<m; i++){

scanf("%d%d%d" ,&a ,&b ,&c);

a = a--;

b = b--;

dist[a][b] = c;

dist[b][a] = c;

}

for (int k=0; k<n; k++){

for (int i=0; i<n; i++){

for (int j=0; j<n; j++){

if (dist[i][k] + dist[k][j] < dist[i][j]){

dist[i][j] = dist[i][k] + dist[k][j];

mid[i][j] = k;

}

}

}

}

}

}