11015 - 05-2 Rendezvous

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

int mat[MAX][MAX];
int koyta_member,koyta_path,a,b,cost,i,j,k,sum,minimum,person,tc=0;
char str[25][12];

void Floyd()
{
    for(k=1; k<=koyta_member; k++)
    {
        for(i=1; i<=koyta_member; i++)
        {
            for(j=1; j<=koyta_member; j++)
            {
                if(mat[i][j]>mat[i][k]+mat[k][j])
                {
                    mat[i][j]=mat[i][k]+mat[k][j];
                }
            }
        }
    }
}


int main()
{
    while(cin>>koyta_member>>koyta_path)
    {
        if(koyta_member==0 && koyta_path==0)
        {
            break;
        }

        for(i=0; i<koyta_member; i++)
        {
            getchar();
            scanf("%s",str[i]);
        }

        for(i=1; i<=koyta_path; i++)
        {
            cin>>a>>b>>cost;
            mat[a][b]=cost;
            mat[b][a]=cost;
        }

        for(i=1; i<=koyta_member; i++)
        {
            for(j=1; j<=koyta_member; j++)
            {
                if(i!=j && mat[i][j]==0)
                {
                    mat[i][j]=Infinity;
                }
            }
        }

        Floyd();

        minimum=999999;
        for(i=1; i<=koyta_member; i++)
        {
            sum=0;
            for(j=1; j<=koyta_member; j++)
            {
                if(mat[i][j]!=Infinity && i!=j)
                {
                    sum+=mat[i][j];
                }
            }
            if(sum<minimum)
            {
                minimum=sum;
                person=i;
            }
        }

        printf("Case #%d : %s\n",++tc,str[person-1]);
        memset(str,'\0',sizeof(str));
        memset(mat,0,sizeof(mat));
    }
    return 0;
}