Solution
輸入是從1開始數的,所以讀入時將u, v 都-1先刷所有最短路
再找最小總和
#include <iostream>
#include <string>
#include <memory.h>
#include <vector>
#define max_num 9999
using namespace std;
int rat[30][30];
vector<string> names;
int main(){
int n, m;
int kase = 1;
while(cin >> n >> m){
if(n == 0)
break;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(i==j)
rat[i][j] = rat[j][i] = 0;
else
rat[i][j] = rat[j][i] = max_num;
for(int i = 0; i < n; i++){
string input;
cin >> input;
names.push_back(input);
}
for(int i = 0; i < m; i++){
int u, v, k;
cin >> u >> v >> k;
rat[u-1][v-1] = rat[v-1][u-1] = k;
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
if(rat[j][k] > rat[j][i] + rat[i][k])
rat[j][k] = rat[j][i] + rat[i][k];
int min = max_num;
int rec;
for(int i = 0; i < n; i++){
int sum = 0;
for(int j = 0; j < n; j++){
sum += rat[i][j];
}
if(sum < min){
min = sum;
rec = i;
}
}
cout << "Case #" << kase++ << " : " << names[rec] << endl;
names.clear();
}
return 0;
}
No comments:
Post a Comment