[백준/C++] 18223번: 민준이와 마산 그리고 건우

문제 & 링크

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

풀이

1. 어떤 변도 음수 가중치를 갖지 않고, 1번 노드에서 V번 노드까지의 최단 경로를 구하기 위해 다익스트라 알고리즘을 사용한다.

2. 인접리스트 형태로 양방향 그래프를 저장한다.

3. 1번 노드에서 다익스트라를 수행한다. 이때 모든 노드까지의 거리를 inf로 초기화하고, 우선순위큐를 사용하여 가장 작은 cost를 가진 노드 순서대로 탐색한다.

4. 탐색 시간을 줄이기 위하여 현재까지의 cost가 해당 노드까지 이동하는 cost보다 크다면 continue를 수행한다.

5. 만약 다음 노드까지의 cost가 해당 노드까지 이동하는 cost보다 작으면 cost 값을 갱신하고, 우선순위큐에 push한다.

6. 3 - 5번까지의 과정을 통해 건우가 있는 위치인 P까지의 거리와 마산의 위치인 V까지의 거리를 저장한다.

7. 3 - 5번까지의 과정을 건우가 있는 위치인 P에서 수행한다.

8. 1에서 P까지 가는 최소 cost + P에서 V까지 가는 최소 cost = 1에서 V까지 가는 최소 cost와 같다면, 건우를 데리고 마산에 갈 수 있다.

코드

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

using namespace std;

vector<pair<int, int>> adj[5001];
int cost[5001];

void dijkstra(int n, int V) {
    fill(cost, cost + V + 1, 123456789);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push({ 0, n });
    cost[n] = 0;

    while (!pq.empty()) {
        int c = pq.top().first;
        int x = pq.top().second;
        pq.pop();

        if (cost[x] < c) continue;

        for (int i = 0; i < adj[x].size(); i++) {
            int nx = adj[x][i].first;
            int nc = c + adj[x][i].second;

            if (cost[nx] > nc) {          
                pq.push({ nc, nx });
                cost[nx] = nc;
            }
        }
    }
}

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

    int V, E, P;
    cin >> V >> E >> P;

    int a, b, c;
    for (int i = 0; i < E; i++) {
        cin >> a >> b >> c;
        adj[a].push_back({ b, c });
        adj[b].push_back({ a, c });
    }

    dijkstra(1, V);

    int costP = cost[P];
    int costV = cost[V];

    dijkstra(P, V);

    int costPV = cost[V];

    if (costV == costP + costPV) cout << "SAVE HIM";
    else cout << "GOOD BYE";
}