(C++) - 백준(BOJ) 18223번 : 민준이와 마산 그리고 건우

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

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

dijkstra문제였습니다.

 

 

📕 풀이방법

📔 입력 및 초기화

 인접그래프를 만들어줍니다. 

 

📔 풀이과정

 1 ~ p까지의 최단거리 + p ~ v까지의 최단거리 <= 1 ~ v까지의 최단거리라면 살려줄 수 있습니다.

이것이 성립하지 않는다면 건우를 거쳐가는 경로가 최단거리가 아니므로 구할 수 없습니다.

 

📔 정답출력

살릴 수 있다면 SAVE HIM , 없다면 GOOD BYE를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using pii = pair<int,int>;
struct Edge {int v, cost; };
int vertexNum, edgeNum, point, dist[5001];
vector <Edge> graph[5001];

int dijkstra(int startPoint, int endPoint){
    memset(dist,INF,sizeof(dist));
    priority_queue <pii, vector<pii>, greater<pii>> pq;
    pq.push({0,startPoint});
    dist[startPoint] = 0;
    while(!pq.empty()){
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if(dist[cur] < cost) continue;
        for(auto nextGraph : graph[cur]){
            int next = nextGraph.v;
            int nextCost = nextGraph.cost;
            if(dist[next] > cost + nextCost){
                dist[next] = cost + nextCost;
                pq.push({dist[next],next});
            }
        }
    }

    return dist[endPoint];
}

int main(){
    cin >> vertexNum >> edgeNum >> point;
    for(int i = 0,a,b,c; i < edgeNum; i++){
        cin >> a >> b >> c;
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }

    if(dijkstra(1,point) + dijkstra(point,vertexNum) <= dijkstra(1,vertexNum)){
        cout << "SAVE HIM";
    }
    else cout << "GOOD BYE";
}