백준 18233 민준이와 마산 그리고 건우

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

아이디어

• 다익스트라를 두번써서 한번 거치고 가는것과 바로 가는것을 비교
• 출발지에서 다익스트라 수행
• 건우 위치에서 다익스트라 수행
• 출발지 -> 마산 == 출발지 -> 건우 + 건우 -> 마산 을 확인

시간복잡도 계산

• 다익스트라 : O(ElgE)
  • E : 1e4
  • 가능

자료구조

• 인접리스트 vector<pair<int, int>> adj[5010]
  • 이떄 양방향임을 조심
• 다익스트라 거리 배열 : int dist[5010]
  • chleorjfl : 1e4 * 5e3= 5e7 > INT 가능

코드(C++)

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
typedef pair<int, int> pi2;
 
vector<pi2> adj[5010];
const int inf = 1e8+10;
int dist[5010];
int dist2[5010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int V,E,P; cin >> V >> E >> P;
    for(int i=0; i<E; i++) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
        adj[b].push_back(make_pair(c,a));
    }
    
    fill(dist, dist+5010, inf);
    fill(dist2, dist2+5010, inf);
    priority_queue<pi2, vector<pi2>, greater<pi2>> pq;
    
    // 1번에서 출발
    dist[1] = 0;
    pq.push(make_pair(dist[1],1));
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        
        if(dist[ei] != ec) continue;
        
        for(auto x : adj[ei]) {
            int nc = x.first;
            int ni = x.second;
            if(dist[ni] > nc + ec) {
                dist[ni] = ec + nc;
                pq.push(make_pair(dist[ni], ni));
            }
        }
    }
    
    dist2[P] = 0;
    pq.push(make_pair(dist2[P],P));
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        
        if(dist2[ei] != ec) continue;
        
        for(auto x : adj[ei]) {
            int nc = x.first;
            int ni = x.second;
            if(dist2[ni] > nc + ec) {
                dist2[ni] = ec + nc;
                pq.push(make_pair(dist2[ni], ni));
            }
        }
    }
    
    if(dist[V] == dist[P] + dist2[V]) cout << "SAVE HIM\n";
    else cout << "GOOD BYE\n";
    
    
    
    return 0;
}
 

문제유형

• 한점 거쳐서 갈경우 최소거리인지 확인
  • E가 V에 비해 상대적으로 작으면(E<V^2), 다익스트라 두번쓰고
  • E가 V에 비해 상대적으로 크면(E > V^2), 플로이드 사용
  • 거쳐간 경우의 거리랑 최소값이 같은지 확인