[BOJ] 13424번 : 비밀 모임(C++)

문제 링크 : 백준 13424번

[문제 접근]

한 정점에서 모든 정점까지의 거리를 구해야하고 음수 가중치는 없기 때문에 전형적인 다익스트라 문제이다.
한 명의 친구당 다익스트라를 한 번씩 해주면 된다.
우선순위 큐를 가중치가 작은 순으로 설정하고 다익스트라 탐색을 한다.
전부 탐색이 끝나면 ans라는 배열에 각 정점까지의 최소 거리인 dist배열을 더해주고 다른 친구도 똑같이 해준다.
이렇게 되면 ans 배열에 모든 친구들의 최소 거리 합이 들어있게 되므로 그 중 최소 값을 정답으로 출력하면 된다.

[소스 코드]

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
int t;
int maxnum = 10000;
typedef pair<int, int> q;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while(t--) {
        int n, m;
        cin >> n >> m;
        vector<q> arr[101];
        int ans[101];
        for(int i=0 ; i<101 ; i++) ans[i] = 0;
        
        for(int i=0 ; i<m ; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            arr[a].push_back(q(b, c));
            arr[b].push_back(q(a, c));
        }
        int k;
        cin >> k;
        for(int i=0 ; i<k ; i++) {
            int s;
            cin >> s;
            int dist[101];
            for(int j=0 ; j<101 ; j++) dist[j] = maxnum;

            priority_queue<q, vector<q>, greater<q> > pq;
            pq.push(q(0, s));
            dist[s] = 0;
            while(!pq.empty()) {
                int cur = pq.top().second;
                pq.pop();

                for(int k=0 ; k<arr[cur].size() ; k++) {
                    int next = arr[cur][k].first;
                    if(dist[next] > dist[cur] + arr[cur][k].second) {
                        dist[next] = dist[cur] + arr[cur][k].second;
                        pq.push(q(dist[next], next));
                    }
                }
            }
            for(int j=1 ; j<=n ; j++) {
                ans[j] += dist[j];
            }
        }

        int result = -1;
        int num;
        for(int i=1 ; i<=n ; i++) {
            if(result == -1 || ans[i]<result) {
                result = ans[i];
                num = i;
            }
        }

        cout << num << "\n";
    }
    


    return 0;
}