[백준 13911] 집 구하기

더미노드를 추가해서 푸는 문제이다.

0인 간선을 추가하는 것이다.

간선 값이 0이니 기존 그래프의 최단거리 탐색에는 아무런 영향을 주지 않는다.

그저 실제로 존재하는 노드는 아니지만, 최단거리 탐색에 드는 시간복잡도 또는 알고리즘 연산 횟수를 줄이기 위해 추가한 노드인 것이다.

 

아래와 같이 모든 맥도날드와 연결된 더미노드 1개와 모든 스타벅스와 연결된 더미노드 1개를 붙여주면 된다.

이로써 더미노드를 시작으로 다익스트라를 돌렸을때 특정 집의 입장에서 갈 수 있는 모든 맥도날드와 스벅을 고려한 최단 거리를 한번의 다익스트라로 구할 수 있게 된다!

그리고 각 더미노드로 부터 모든 노드까지의 최단거리를 구해주면 된다.

만약 맥도날드 더미노드에서 다익스트라를 돌리면 집 입장에서는 자신과 가장 가까운 맥도날드의 거리가 찍힐 것이다.

똑같이 스타벅스 더미노드에서 돌리면 각 집 입장에서 자신과 가장 가까운 스타벅스 거리가 찍힐 것이다.

 

따라서 더미노드에서 다익스트라 두 번 돌리고 각 집들의 가장 가까운 맥도날드 거리 + 가장 가까운 스타벅스 거리를 더한 값 중 최소값을 구해주면 된다.

 

---

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

#define SIZE 10003
#define INF int(1e9)

using namespace std;

int V, E, M, S;
int u, v, w;
int x, y;

vector<vector<pair<int, int>>> graph(SIZE);
unordered_set<int> mcdonalds;
unordered_set<int> starbucks;

int ans = INF;
// dist[0] => 맥도날드 더미노드에서 모든 집까지의 거리
// dist[1] => 스타벅스 더미노드에서 모든 집까지의 거리
int dist[2][SIZE];

// idx 0이면 맥도날드 1이면 스타벅스
void solve(int house, int idx)
{
    for (int i = 0; i <= V; i++)
    {
        dist[idx][i] = INF;
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, house));
    dist[idx][house] = 0;

    while (!pq.empty())
    {
        auto [total, cur] = pq.top();
        pq.pop();

        // 조사할 필요가 없다면
        if (total > dist[idx][cur])
        {
            continue;
        }

        for (int i = 0; i < graph[cur].size(); i++)
        {
            int next = graph[cur][i].first;
            int cost = graph[cur][i].second;

            // 조사할 필요가 있다면
            if (total + cost < dist[idx][next])
            {
                dist[idx][next] = total + cost;
                pq.push(make_pair(total + cost, next));
            }
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> V >> E;
    for (int i = 0; i < E; i++)
    {
        cin >> u >> v >> w;
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w));
    }

    int a;
    cin >> M >> x;

    // 더미노드와 모든 맥도날드 연결
    for (int i = 0; i < M; i++)
    {
        cin >> a;
        mcdonalds.insert(a);
        graph[10001].push_back(make_pair(a, 0));
    }

    cin >> S >> y;
    // 더미노드와 모든 스타벅스 연결
    for (int i = 0; i < S; i++)
    {
        cin >> a;
        starbucks.insert(a);
        graph[10002].push_back(make_pair(a, 0));
    }

    // 맥도날드 더미노드에서 모든 노드까지의 최단거리
    solve(10001, 0);
    // 스타벅스 더미노드에서 모든 노드까지의 최단거리
    solve(10002, 1);

    int ans = INF;
    for (int i = 1; i <= V; i++)
    {
        // 일반 집이 될 수 있다면
        if (mcdonalds.find(i) == mcdonalds.end() && starbucks.find(i) == starbucks.end())
        {
            // 맥세권 스세권을 만족한다면
            if (dist[0][i] <= x && dist[1][i] <= y)
            {
                ans = min(ans, dist[0][i] + dist[1][i]);
            }
        }
    }

    if (ans == INF)
        cout << "-1";
    else
        cout << ans;

    return 0;
}

 

 

아래는 시간초과 났던거.

집 입장에서 돌려서 모든 집에 대한 다익스트라를 하였다.

 

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

#define SIZE 10001
#define INF int(1e9)

using namespace std;

int V, E, M, S;
int u, v, w;
int x, y;

vector<vector<pair<int, int>>> graph(SIZE);
unordered_set<int> mcdonalds;
unordered_set<int> starbucks;

int ans = INF;

void solve(int house)
{
    int dist[SIZE];

    for (int i = 0; i <= V; i++)
    {
        dist[i] = INF;
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, house));
    dist[house] = 0;

    while (!pq.empty())
    {
        auto [total, cur] = pq.top();
        pq.pop();

        // 조사할 필요가 없다면
        if (total > dist[cur])
        {
            continue;
        }

        for (int i = 0; i < graph[cur].size(); i++)
        {
            int next = graph[cur][i].first;
            int cost = graph[cur][i].second;

            // 조사할 필요가 있다면
            if (total + cost < dist[next])
            {
                dist[next] = total + cost;
                pq.push(make_pair(total + cost, next));
            }
        }
    }

    int minMcdonals = INF;
    int minStarbucks = INF;
    for (int i = 1; i <= V; i++)
    {
        // 특정 정점이 맥도날드이고 맥세권 거리 내이면
        // 최소 맥세권 거리 최신화
        if (mcdonalds.find(i) != mcdonalds.end() && dist[i] <= x)
        {
            minMcdonals = min(minMcdonals, dist[i]);
        }
        // 특정 정점이 스타벅스이고 맥세권 거리 내이면
        // 최소 스세권 거리 최신화
        if (starbucks.find(i) != starbucks.end() && dist[i] <= y)
        {
            minStarbucks = min(minStarbucks, dist[i]);
        }
    }

    // cout << "[" << house << "]\n";
    // for (int i = 1; i <= V; i++)
    // {
    //     if (dist[i] == INF)
    //         cout << "INF ";
    //     else
    //         cout << dist[i] << " ";
    // }
    // cout << "\n";

    // cout << "[" << house << "] 일때 맥세권:" << minMcdonals << " 스세권:" << minStarbucks << "\n";
    ans = min(ans, minMcdonals + minStarbucks);
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> V >> E;
    for (int i = 0; i < E; i++)
    {
        cin >> u >> v >> w;
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w));
    }

    cin >> M >> x;
    int a;
    for (int i = 0; i < M; i++)
    {
        cin >> a;
        mcdonalds.insert(a);
    }

    cin >> S >> y;
    for (int i = 0; i < S; i++)
    {
        cin >> a;
        starbucks.insert(a);
    }

    for (int house = 1; house <= V; house++)
    {
        // 일반 집이 될 수 있는 곳이면
        if (mcdonalds.find(house) == mcdonalds.end() && starbucks.find(house) == starbucks.end())
        {
            solve(house);
        }
    }

    if (ans == INF)
        cout << "-1";
    else
        cout << ans;

    return 0;
}