[Algorithm] 백준 18233 민준이와 마산 그리고 건우 - C++, 다익스트라

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

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <limits>
#include <cstring>
using namespace std;

int v, e, minjun;
int costs[5001];
vector<pair<int, int>> edges[5001];

int Djikstra(int start, int finish){
    for(int i = 0; i <= v; i++){
        costs[i] = INT32_MAX;
    }

    // Djikstra
    priority_queue<pair<int, int>> q; // cost, node
    q.push({0, start});
    costs[start] = 0;

    while (!q.empty()){
        int curCost = -q.top().first;
        int curPos = q.top().second;
        q.pop();

        if(costs[curPos] < curCost)
            continue;

        for(int i = 0; i < edges[curPos].size(); i++){
            int nextCost = curCost + edges[curPos][i].second;
            int nextPos = edges[curPos][i].first;

            if(costs[nextPos] > nextCost){
                costs[nextPos] = nextCost;
                q.push({-nextCost, nextPos});
            }
        }
    }

    return costs[finish];
}

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> v >> e >> minjun;
    for(int i = 0; i <= v; i++){
        costs[i] = INT32_MAX;
    }
    for(int i = 0; i < e; i++){
        int a, b, c;
        cin >> a >> b >> c;

        edges[a].push_back({b, c});
        edges[b].push_back({a, c});
    }

    int minDist = Djikstra(1, v);
    int startToMinjun = Djikstra(1, minjun);
    int minjunToFin = Djikstra(minjun, v);
    
    if(minDist == (startToMinjun + minjunToFin)) 
        cout << "SAVE HIM\n";
    else
        cout << "GOOD BYE\n";
}

---

 처음에는 경로 추적인가 했지만 실제로는 여러 최단 경로가 나올 가능성이 있습니다. 그래서 '전체 다익스트라 = (출발에서 민준이까지 다익스트라) + (민준이에서 마산까지 다익스트라)' 라면 픽업할 수 있고 아니면 픽업할 수 없는걸로 하면 풀립니다.