|
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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
#include <iostream> #include <string.h> #include <vector> #include <map> #define ll long long #define INF 1000000000 using namespace std; int graph[25][25]; int N,M,MiN; int sum[25]; map<int,string> m; int main() { int t,kase=1; int a,b,c,res; string s; //cin>>t; while(cin>>N) { cin>>M; if(N==0 ) break; //mp.clear(); m.clear(); int x=1; for(int i=1;i<25;i++) { sum[i]=0; for(int j=1;j<25;j++) { graph[i][j]=INF; if(i==j) graph[i][j]=0; } } for(int i=0;i<N;i++) { cin>>s; m[i+1]=s; } for(int i=0;i<M;i++) { cin>>a>>b>>c; graph[a][b]=c; graph[b][a]=c; } MiN = INF; for(int k=1;k<=N;k++) { for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { if(graph[i][j]>(graph[i][k]+graph[k][j])) graph[i][j] = (graph[i][k]+graph[k][j]); } } } for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) sum[i]+=graph[i][j]; if(sum[i]<MiN) { MiN = sum[i]; res = i; } } cout<<"Case #"<<kase++<<" : "<<m[res]<<"\n"; } return 0; } |