[백준] 13911 - 집 구하기

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

13911번: 집 구하기

 

간략하게 요약하면 임의의 정점에서 서로 다른 두 정점까지의 거리의 최솟값을 구하는 문제이다.

모든 맥도날드와 스타벅스 정점에서 다익스트라를 실행하면 TLE가 나기 때문에 다른 방법을 구사해야 한다.

 

핵심은 다음과 같다.

맥도날드에 이어진 가상의 정점과,

스타벅스에 이어진 가상의 정점을 생성하고 가중치가 0인 간선으로 연결하는 것이다.

 

이 예제에서 N + 1(9) 번 정점을 만들어서

9 -> 1

9 -> 5

간선을 가중치가 0인 간선으로 연결해보자.

또한 N + 2(10) 번 정점을 만들어서

10 -> 8

간선을 가중치가 0인 간선으로 연결해보자.

 

이렇게 하면 모든 맥도날드에서 각 정점에 도달하는 최단 거리와 모든 스타벅스에서 각 정점에 도달하는 최단 거리를 구할 수 있다.

즉, 많은 맥도날드와 많은 스타벅스 정점을 각각 하나의 정점으로 처리하는 테크닉을 구사한 것이다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<pair<int, int>>> v;
vector<int> mac, star;
int n, e, mc, md, sc, sd;
int house[10001];

vector<int> dijk(int start)
{
    vector<int> dis(n + 3, 987654321);
    priority_queue<pair<int, int>> pq;

    pq.push({0, start});
    dis[start] = 0;

    while (!pq.empty())
    {
        int node = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();

        if (dis[node] < cost)
        {
            continue;
        }

        for (auto &i : v[node])
        {
            int nxCost = cost + i.second;
            if (dis[i.first] > nxCost)
            {
                dis[i.first] = nxCost;
                pq.push({-nxCost, i.first});
            }
        }
    }
    return dis;
}

int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> e;
    v.resize(n + 3);
    for (int i = 0; i < e; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }

    cin >> mc >> md;
    for (int i = 0; i < mc; i++)
    {
        int a;
        cin >> a;
        house[a] = -1;
        v[n + 1].push_back({a, 0});
    }
    cin >> sc >> sd;
    for (int i = 0; i < sc; i++)
    {
        int a;
        cin >> a;
        house[a] = -1;
        v[n + 2].push_back({a, 0});
    }

    vector<int> mDis = dijk(n + 1);
    vector<int> sDis = dijk(n + 2);
    int ans = 987654321;
    for (int i = 1; i <= n; i++)
    {
        if (house[i] == -1)
        {
            continue;
        }
        if (mDis[i] <= md && sDis[i] <= sd)
        {
            ans = min(ans, mDis[i] + sDis[i]);
        }
    }

    if (ans == 987654321)
    {
        cout << -1;
    }
    else
    {
        cout << ans;
    }
}