백준 13424:비밀 모임

https://www.acmicpc.net/problem/13424

백준 13424번 비밀 모임이예요. 해리포터 보고싶다 이번 문제는 모든 친구들로부터 가장 짧은 곳을 찾아야하기때문에 각 테스트케이스마다 K번씩 탐색해야해요. 그래서 minimum배열에 각점에 대한 최단경로 정보들을 저장해 두고 마지막에 친구들이 가장 편하게? 올수 있는 방을 골라주면 됩니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
#define endl '\n'
#define INF (static_cast<int>(1e9))
typedef pair<int, int> PAIR;
int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    for (int testCase = 0; testCase < T; testCase++) {
        int N, M; cin >> N >> M;
 
        vector<vector<PAIR>> graph(N);
        for (int i = 0; i < M; i++) {//양방향 그래프
            int a, b, c; cin >> a >> b >> c;
            graph[a - 1].push_back(PAIR(b - 1, c));
            graph[b - 1].push_back(PAIR(a - 1, c));
        }
 
        int K; cin >> K;//start에 저장된 점부터 탐색해요
        vector<int> start(K);
        for (int& i : start) {
            cin >> i; i--;
        }
 
        vector<vector<int>> minimum;//최솟값을 계산하기위한 배열
        for (int i = 0; i < K; i++) {//K개의 점에서 탐색해요
            priority_queue<PAIR, vector<PAIR>, greater<PAIR>> pq;
            vector<bool> visited(N, false);
            vector<int> cost(N, INF);
            pq.push(PAIR(0, start[i]));
            cost[start[i]] = 0;
 
            while (!pq.empty()) {//다익스트라 알고리즘
                int cur;
                do {
                    cur = pq.top().second; pq.pop();
                } while (!pq.empty() && visited[cur]);
 
                if (visited[cur]) break;
                visited[cur] = true;
 
                for (auto& n : graph[cur]) {
                    int next = n.first, distance = n.second;
                    if (cost[next] > cost[cur] + distance) {
                        cost[next] = cost[cur] + distance;
                        pq.push(PAIR(cost[next], next));
                    }
                }
            }
            //시작점으로부터의 최단거리를 저장해요
            minimum.push_back(cost);
        }
 
        int minRoom = INF, room;
        for (int c = 0; c < N; c++) {//각 점에 대하여
            int temp = 0;
            for (int r = 0; r < K; r++) {
                temp += minimum[r][c];
            }
            //최솟값을 계산해요
            if (minRoom > temp) {
                minRoom = temp;
                room = c;
            }
        }
 
        cout << room + 1 << endl;
    }
 
 
 
    return 0;
}