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

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

---

풀이

다익스트라를 이용해서 푼다.

1→P→N 순으로 가는 최단거리가 1→N 최단거리보다 작거나 같으면 SAVE HIM을 아니면 GOOD BYE를 출력한다 

 

 

 

코드

#include <bits/stdc++.h>
#define V 5001
using namespace std;

vector<pair<int,int>> adj[V];

int n,e,p;

int Dijkstra(int src, int nend){
   vector<int> dist(V, 100000000);
   dist[src] = 0;
   priority_queue<pair<int,int>> q;
   q.push(make_pair(0,src));
   
   while(!q.empty()){
       int cost = -q.top().first;
       int node = q.top().second;
       q.pop();
       
       if(dist[node] < cost) continue;
       
       for(int i = 0; i < adj[node].size(); i++){
           int nextNode = adj[node][i].first;
           int nextCost = adj[node][i].second + cost;
           
           if(dist[nextNode] > nextCost){
               dist[nextNode] = nextCost;
               q.push(make_pair(-nextCost, nextNode));
           }
       }
   }
   return dist[nend];
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> e >> p;
    int b,nb,c;
    for(int i =0 ; i < e; i++){
        cin >> b >> nb >> c;
        adj[b].push_back(make_pair(nb,c));
        adj[nb].push_back(make_pair(b,c));
    }
    int a1 = Dijkstra(1,n);
    int a2 = Dijkstra(1,p) + Dijkstra(p,n);
    if(a1 == a2){
        cout << "SAVE HIM";
    }
    else if(a1 < a2){
        cout << "GOOD BYE";
    }
    else if (a1 > a2){
        cout << "SAVE HIM";
    }
    return 0;
}