3075 - Astromeeting

미팅하는 사람들이 어떤 은하 k로 가는 비용이 최소가 되는 은하 k를 찾는 문제이다.
그러기 위해선 모든 정점 간의 최단 거리를 구해야하므로, 플로이드 와샬 알고리즘을 썼다.

이제 모든 정점 간의 최단 거리는 구해졌고, (한 정점 K 에서 미팅을 하는 사람의 은하 i)들의 각 비용의 합이 최소가 되는 순간 미팅 장소 은하 K를 갱신했다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

int main(){
    int i, j, k, T;
    scanf("%d", &T);
    while(T--){
        int n, p, q;
        scanf("%d %d %d", &n, &p, &q);
        int members[100]={}, astro[101][101];
        for(i=0; i<p; ++i){
            for(j=0; j<p; ++j){
                if(i == j) astro[i][j] = 0;
                else astro[i][j] = INF;
            }
        }
        for(i=0; i<n; ++i) scanf("%d", &members[i]);
        for(i=0; i<q; ++i){
            int u, v, d;
            scanf("%d %d %d", &u, &v, &d);
            astro[u-1][v-1] = astro[v-1][u-1] = d;
        }
        
        for(k=0; k<p; ++k){
            for(i=0; i<p; ++i){
                for(j=0; j<p; ++j){
                    if(astro[i][k]+astro[k][j] < astro[i][j])
                        astro[i][j] = astro[i][k]+astro[k][j];
                }
            }
        }
        
        int meetingPoint=0, minCost=987654322;
        for(i=0; i<p; ++i){
            int cost = 0;
            for(j=0; j<n; ++j){
                if(astro[members[j]-1][i] == INF){
                    cost = INF;
                    break;
                }
                cost += astro[members[j]-1][i] * astro[members[j]-1][i];
            }
            
            if(minCost > cost){
                minCost = cost;
                meetingPoint = i+1;
            }
        }
        printf("%d %d\n", meetingPoint, minCost);
    }
    return 0;
}