백준 #1238 파티

BOJ #1238 - 파티

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

# 문제 분류

최단 경로 찾기 (Dijkstra Algorithm)

풀이 접근 방법

input size가 크므로 Dijkstra 알고리즘을 사용한다.
각각의 노드마다 Dijkstra하면 되므로, n번 돌리면 $O(VE\log V)$ 이므로 가능하다.

→ 사실 엄밀히 말하면 $O_{worst}(EV+ V^2 * \log V)$ 긴 하다 ,, 그래도 Floyd-Warshall 보다는 훨씬 빠르다!
그래서 dist[i][X] + dist[X][i]가 학생 i 가 파티에 참석한 후 돌아오기 필요한 거리이므로 그 중 제일 긴 것 갱신.

참고할 만한 포스트를 보면 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;
}