BOJ #1238 - 파티

https://icpc.me/1238

# 문제 분류
최단 경로 찾기 (Dijkstra Algorithm)

풀이 접근 방법 :

 

1. input size가 크므로 Dijkstra 알고리즘을 사용한다.

2. 각각의 노드마다 Dijkstra하면 되므로, n번 돌리면 O(VElogV)이므로 가능하다.

→ 사실 엄밀히 말하면 Oworst(EV+ V^2 * logV)긴 하다 ,, 그래도 Floyd-Warshall 보다는 훨씬 빠르다!

3. 그래서 dist[i][X] + dist[X][i]가 학생 i 가 파티에 참석한 후 돌아오기 필요한 거리이므로 그 중 제일 긴 것 갱신.

---

https://hsp1116.tistory.com/44 포스트를 보면

Floyd-Warshall 을 가지치기해서 시간을 줄이는 방법이나,

인접 리스트로 그래프를 표현한 후, 간선들을 뒤집어서 Dijkstra 두번만에 구하는 방법도 있다고 한다.

나는 벡터가 좋아서,,, 그래도 Dijkstra 두번은 정말 간편하고 참신한 방법인 것 같다.

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
 
using namespace std;
typedef pair<int, int> p;
 
int INF = 1e9;
int N, M, X, s, e, t, res, D[1010][1010];;
priority_queue<p, vector<p>, greater<p>> pq[1010];
vector<p> v[1010];
 
int main() {
    scanf("%d %d %d", &N, &M, &X);
    for(int i=1; i<=M; i++){
        scanf("%d %d %d", &s, &e, &t);
        v[s].push_back(make_pair(e, t));
    }
 
    for(int i=1; i<=N; i++){
        pq[i].push(make_pair(0, i));
        bool chk[1010] = {0};
        for(int j=0; j<=N; j++) D[i][j] = INF;
 
        D[i][i] = 0;
 
        while(!pq[i].empty()){
            int u = pq[i].top().second;
            pq[i].pop();
 
            if(chk[u]) continue;
            chk[u] = true;
 
            for(int j=0; j<v[u].size(); j++){
                int w = v[u][j].first;
                int d = v[u][j].second;
 
                if(D[i][w] > D[i][u] + d){
                    D[i][w] = D[i][u] + d;
                    pq[i].push(make_pair(D[i][w], w));
                }
            }
        }
    }
 
    for(int i=1; i<=N; i++){
        res = max(res, D[i][X] + D[X][i]);
    }
 
    printf("%d", res);
 
    return 0;
}