[C++] 純文本查看 復制代碼
#include<iostream>
#include<cstdio>
#define INF 1000000000
using namespace std;
int n,m;
int dist[30][30];
string name[100];
void FW()
{
for(int j = 1 ; j <= n ; j++)
for(int i = 1 ; i <= n ; i++)
for(int k = 1 ; k <= n ; k++)
dist[k] = min(dist[k], dist[j]+dist[j][k]);
}
int main()
{
for(int time = 1 ; ; time++)
{
cin >> n >> m;
if(n==0 && m==0)
return 0;
int a,b,w;
for(int i = 1 ; i <= n ; i++)
cin >> name;
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
dist[j] = INF;
for(int i = 1 ; i <= n ; i++)
dist = 0;
for(int i = 1 ; i <= m ; i++)
{
cin >> a >> b >> w;
if(w < dist[a])
{
dist[a] = w;
dist[a] = w;
}
}
FW();
int ans, min_sum = INF;
for(int i = 1 ; i <= n ; i++)
{
int sum = 0;
for(int j = 1 ; j <= n ; j++)
{
sum += dist[j];
// printf("%d %d = %d\n",i,j,dist[j]);
}
// cout << "sum = " << sum << endl;
if(sum < min_sum)
{
min_sum = sum;
ans = i;
}
}
cout << "Case #" << time << " : " << name[ans] << endl;
}
return 0;
}