d282. 11015 - 05-2 Rendezvous -- UVa11015 | From: [219.85.192.97] | 發表日期 : 2014-08-15 00:08

#include <stdio.h>

int main(void)

{

char name[25][13];

int a, b, c, d, e, f=1, l[100], n, m, mid[25][25], dist[25][25];

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

d = 10000000;

e = 0;

if (n == 0){

break;

}

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

scanf ("%s" ,&name[i]);

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

mid[i][j] = -1;

dist[i][j] = 1000000000;

}

dist[i][i] = 0;

}

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

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

a--;

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;

}

}

}

}

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

l[i] = 0;

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

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

}

}

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

if ( l[i] < d ){

d = l[i];

e = i;

}

}

printf("Case #%d : %s\n" ,f ,name[e]);

f++;

}

}