문제

13911번: 집 구하기

풀이

최단거리를 구해야하는 문제이다.
다익스트라 알고리즘을 이용해서 해결할 수 있는데, 노드의 개수가 많아 모든 노드에 대해서 다익스트라 알고리즘을 적용하여 맥도날드와 스타벅스까지의 최단 거리를 구할 수 없다.

각각의 집에서 맥도날드와 스타벅스까지의 거리를 구하는 것이 아닌 맥도날드와 스타벅스에서 각각의 집까지의 최단 거리를 구한다. 이렇게 한다면 다익스트라를 2번 사용하여 최단거리를 구할 수 있다.
맥도날드, 스타벅스 이기만 하면 되기 때문에 어디 위치에 있든 상관없이 같은 맥도날드, 혹은 스타벅스로 취급하여 처리한다.

다익스트라 알고리즘에서 시작 위치를 모든 맥도날드, 모든 스타벅스로 하여 최단거리를 구하면 된다.
모든 맥도날드에서 동시에 출발하여 모든 노드에 대해 최단 거리를 측정한다는 것이다.

void dijkstar(vector<int>& start, vector<int>& dist){
    priority_queue<Node> pq;
    dist.assign(v+1, INF);
    for (auto s: start){
        dist[s] = 0;
        pq.push({0, s});
    }
    while (!pq.empty()){
        int cur = pq.top().second;
        int weight = - pq.top().first;
        pq.pop();

        if (dist[cur] < weight) continue;
        for (auto edge : graph[cur]){
            int next = edge.second;
            int nextWeight = weight + edge.first;

            if( nextWeight < dist[next] ){
                dist[next] = nextWeight;
                pq.push({ -nextWeight, next });
            }
        }
    }
}

다익스트라를 두 번 사용하여 맥도날드에서의 거리, 스타벅스에서의 거리를 구한 후 두 거리배열을 비교하며 조건을 만족하는 최단거리에 위치하는 집을 구했다.

dijkstar(isMac, distFromMac);
dijkstar(isStar, distFromStar);
    
int minDist = INF;
for (int i=1; i<v+1; i++){
    if (!isHouse[i]) continue;
    if (distFromMac[i] > macMinLimit || distFromStar[i] > starMinLimit) continue;
    if (minDist > distFromMac[i] + distFromStar[i]){
        minDist = distFromMac[i] + distFromStar[i];
    }
}

코드

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

#define Node pair<int, int>
#define INF 100000001

using namespace std;

int v, e;
int macCnt, starCnt;
int macMinLimit;
int starMinLimit;
vector<int> distFromMac;
vector<int> distFromStar;
vector<int> isMac;
vector<int> isStar;
vector<bool> isHouse;
vector<vector<Node>> graph;

void dijkstar(vector<int>& start, vector<int>& dist){
    priority_queue<Node> pq;
    dist.assign(v+1, INF);
    for (auto s: start){
        dist[s] = 0;
        pq.push({0, s});
    }
    while (!pq.empty()){
        int cur = pq.top().second;
        int weight = - pq.top().first;
        pq.pop();

        if (dist[cur] < weight) continue;
        for (auto edge : graph[cur]){
            int next = edge.second;
            int nextWeight = weight + edge.first;

            if( nextWeight < dist[next] ){
                dist[next] = nextWeight;
                pq.push({ -nextWeight, next });
            }
        }
    }
}

int main () {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> v >> e;
    isHouse = vector<bool>(v+1, true);
    graph.assign(v+1, vector<Node>());
    while (e--){
        int a, b, w;
        cin >> a >> b >> w;
        graph[a].push_back({w, b});
        graph[b].push_back({w, a});
    }

    cin >> macCnt >> macMinLimit;
    for (int i=0; i<macCnt; i++){
        int mac;
        cin >> mac;
        isHouse[mac] = false;
        isMac.push_back(mac);
    }

    cin >> starCnt >> starMinLimit;
    for (int i=0; i<starCnt; i++){
        int star;
        cin >> star;
        isHouse[star] = false;
        isStar.push_back(star);
    }

    dijkstar(isMac, distFromMac);
    dijkstar(isStar, distFromStar);
    
    int minDist = INF;
    for (int i=1; i<v+1; i++){
        if (!isHouse[i]) continue;
        if (distFromMac[i] > macMinLimit || distFromStar[i] > starMinLimit) continue;
        if (minDist > distFromMac[i] + distFromStar[i]){
            minDist = distFromMac[i] + distFromStar[i];
        }
    }
    if (minDist == INF) minDist = -1;
    cout << minDist << endl;

    return 0;
}