Aizu0189 Convenient Location（多源最短路）

题意:求某一点到其他所有点的最短路径之和，输出该点与和。

注意Floyd可以求多源最短路径，而Dijkstra只能求单源。

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<map>

 #include<set>

 #define LL long long

 #define maxn 100005

 #define MOD 1e9+7

 #define INF 0x3f3f3f3f

 typedef long long ll;

 using namespace std;

 int n, D[][], x, y, z, maxm, mini;

 int main()

 {

     while(cin >> n, n){

         maxm = -INF;

         for(int i = ; i < ; i++){

             for(int j = ; j < ; j++){

                 D[i][j] = INF;

             }

         }

         for(int i = ; i < n; i++){

             cin >> x >> y >> z;

             D[x][y] = min(D[x][y], z);

             D[y][x] = D[x][y];

             maxm = max(maxm, max(x, y));

         }

         maxm++;

         for(int i = ; i < ; i++){

             D[i][i] = ;

         }

         for(int k = ; k < maxm; k++){

             for(int i = ; i < maxm; i++){

                 for(int j = ; j < maxm; j++){

                     if(D[i][j] > D[i][k]+D[k][j]){

                         D[i][j] = D[i][k]+D[k][j];

                     }

                 }

             }

         }

         mini = INF;

         int loc = -;

         for(int i = ; i < maxm; i++){

             int sum = ;

             for(int j = ; j < maxm; j++){

                 sum += D[i][j];

             }

             if(mini > sum){

                 mini = sum;

                 loc = i;

             }

         }

         cout << loc << " " << mini << endl;

     }

     return ;

 }