【UVa】11015 Rendezvous

Problem here

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;
}