11015 - 05-2 Rendezvous

#include<iostream>
#include<cstdio>
#include<cstring>
#define M 25
#define MAX 1000000
using namespace std;

char Place[M][12];
int W[M][M];

int main()
{
    int n,m,i,j,k,c=1,x,y,z,mn,tc,mc;
    string name;
    //freopen("in.txt","r",stdin);

    while(scanf("%d%d\n",&n,&m)&&(n|m))
    {       
        for(i=1;i<=n;i++)
            for(j=1;j<=i;j++)
                W[i][j] = W[j][i] = MAX;

        for(i=0;i<=n;i++)W[i][i] = 0;

        for(i=1;i<=n;i++)
            gets(Place[i]);

        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            W[x][y] = W[y][x] = z;
        }
       
        //Floyed Warshall
        for(k=1;k<=n;k++)
            for(i=1;i<=n;i++)
                for(j=1;j<=n;j++)
                {
                    x = W[i][k]+W[k][j];
                    if(x < W[i][j])
                        W[i][j] = x;
                }
        mc = 2147483647;mn = 1;
        for(i=1;i<=n;i++)
        {
            tc = 0;
            for(j=1;j<=n;j++)
                tc += W[i][j];
            if(tc<mc)
                mc = tc,mn = i;
        }
        printf("Case #%d : %s\n",c++,Place[mn]);
    }
    return 0;
}