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

문제 링크 : [백준]민준이와 마산 그리고 건우(18223)

문제 설명

1번 노드에서 V번까지 가는 최단거리가 1번에서 P번 노드를 거쳐 V번 노드까지 가는 최단거리보다 작거나 같은지 판별하세요.

입력

V(노드의 갯수, 1 <= V <= 5,000)
M(간선의 갯수, 1 <= M <= 10,000)
A_i B_i C_i(출발 노드, 도착 노드, 비용, 1 <= C_i <= 10,000)

6 7 4
1 2 1
1 3 1
2 3 10
3 4 1
3 5 2
4 5 1
5 6 1

출력

SAVE HIM

카테고리

#다익스트라

시간 복잡도 상한

O(M²)

해결 방법

1. 1 -> V까지의 최단거리는 1번에서 시작하는 다익스트라를 통해 O(M * logM)만에 구할 수 있습니다.
2. 양방향 그래프이기 때문에, 1 -> P의 최단거리는 P -> 1까지의 최단거리와 같습니다.
3. 따라서 1 -> P -> V 로 가는 최단 거리는, P에서 시작하는 다익스트라를 구합니다.
4. 그러면 P -> 1로 가는 최단거리 + P -> V로 가는 최단거리를 더하면 됩니다.

시간복잡도

O(M * logM)

코드

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<string.h>
#define N 5001
using namespace std;
typedef pair<int,int>P;
int n,m,p,a,b,c,d[N],e[N],w[N];
vector<P>v[N];
priority_queue<P,vector<P>,greater<P>>q;
void r(int s,int d[]){
    memset(w,0,sizeof(w));
    q.push({0,s});
    while(!q.empty()){
        P x=q.top();q.pop();
        if(w[x.second])continue;
        w[x.second]=1;
        d[x.second]=x.first;
        for(P y:v[x.second])if(!w[y.second])q.push({x.first+y.first,y.second});
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&p);
    while(m--){
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back({c,b});
        v[b].push_back({c,a});
    }
    r(1,d);
    r(p,e);
    printf("%s",d[n]<e[1]+e[n]?"GOOD BYE":"SAVE HIM");
}