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

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

 

 

이 문제는 N개의 노드가 주어지고 M개의 간선이 주어졌으며 건우의 위치가 입력이 주어진다.

이후 M개의 그래프의 간선이 주어질때

 

1번 노드에서 N번 노드까지 최단경로가 1번 노드에서 건우가 있는 위치 + 건우가 있는 위치 -> N의 최단경로가

이상인지 아닌지만 확인하면 되는 문제이다.

 

 

즉 최단거리를 구해야하기 때문에 다익스트라 알고리즘을 사용하여 최단거리를 구하고

P(건우 위치)에서부터 다시 다익스트라 알고리즘을 사용하여 N까지의 최단경로를 구해서 비교하면

쉽게 풀 수 있다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int V, E, P;
vector<vector<pii>> v(5001);
int dist[5001];
vector<int> tmp;

void dijkstra(int x) {
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, x});        // 비용, 정점
    dist[x] = 0;

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

        if(dist[Node] < cost) continue;

        for(auto it : v[Node]) {
            int NextNode = it.first;
            int NextCost = cost + it.second;

            if(dist[NextNode] > NextCost) {
                pq.push({NextCost, NextNode});
                dist[NextNode] = NextCost;
            }
        }
    }
}

void Init() {
    for(int i = 1; i <= V; i++) {
        dist[i] = MAX;
    }
}

void solve() {
    Init();

    dijkstra(1);

    int gunwoo = dist[P];
    int end = dist[V];

    Init();
    dijkstra(P);

    if(end == gunwoo + dist[V]) cout << "SAVE HIM";
    else cout << "GOOD BYE";
}

void input() {
    cin >> V >> E >> P;

    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});
    }
}

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

    input();
    solve();
}