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

문제링크 : https://www.acmicpc.net/problem/18223

18223번: 민준이와 마산 그리고 건우

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pil pair <int, int>

int V, E, P;
int point[5001];
vector<pil> edges[5001];

void dijkstra(int start)
{
    priority_queue<pil, vector<pil>, greater<pil>> pq; //값이 작을수록 우선순위를 갖는 최소힙
    
    for(int i= 1; i<=V; i++)
    {
        point[i] = MAX;
    }

    pq.push({start, 0}); //시작점과 해당 비용
    point[start]=0;  //출발점

    while(!pq.empty())
    {
        int cur = pq.top().first;   //정점
        int dist = pq.top().second; //거리(비용)
        pq.pop();

        for(int i=0; i<edges[cur].size(); i++)
        {
            int next = edges[cur][i].first;  //다음 정점
            int cost = edges[cur][i].second; //해당 비용

            if(point[next] > dist + cost)  //다음 정점의 비용값 갱신
            {
                point[next] = dist + cost;  //기존 비용 + 다음 비용
                pq.push({next, point[next]});  //다음 정점과 해당 비용 값을 기준으로 시작
            }
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> V >> E >> P;
    while(E--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[a].push_back({b, c});
        edges[b].push_back({a, c});
    }

    dijkstra(1); //시작점을 1로

    int toV = point[V];  // ~ 목적지
    int toP = point[P];  // ~ 건우 위치

    dijkstra(P);  //시작점을 P로 

    int PtoV = point[V];  //건우 ~ 목적지

    if(toP + PtoV <= toV)  
    {
        cout << "SAVE HIM";
    }
    else
    {
        cout << "GOOD BYE";
    }

    return 0;
}

가중치를 가진 그래프의 한 정점에서 다른 모든 정점으로의 최단거리를 구하는 다익스트라 문제이다.

문제자체가 다익스트라를 설명하는 것이나 다름없어서 다익스트라를 모른다면 풀기 힘들 것 같다.