BOJ 1238 파티

처음엔 플로이드 워셜로 시도했다. 플로이드 워셜이 N^3 인데 N 이 1000 이고 대충 1초 정도를 예상했음. 그런데 시간초과가 나서 다익스트라로 AC 를 받았다. (32ms) 그런데 0ms 가 기록에 있는 걸 보고 풀이를 봤는데, 다익스트라로 생각지 못한 풀이가 있어서 남겨봄.

* 참고로 플로이드워셜로도 최적화하면 풀리긴 함.  

---

가장 먼저 떠오른건 플로이드 워셜 알고리즘이었다. 왜냐하면 다익스트라는 한점에서 다른 모든 점까지의 최단거리를 구하는 알고리즘인데, 이번 문제의 조건은 모든 점에서 특정 점까지의 최단거리를 구해야하니까 적절하지 않다고 생각했음.

 

그런데 다익스트라는 한점에서 다른 모든 지점으로의 최단거리 뿐만 아니라

 

한 점으로 도착하는 다른 모든 점에서부터의 최단거리 또한 구할 수 있다.  !!!

 

바로 역방향 그래프를 이용하면 된다. 

 

간선의 방향을 역방향으로 뒤집기만 하면, 한점에서 출발하는 것이 아니라 도착하는 그래프로 바뀌게 되고, 결과값또한 한점에서 출발해서 다른 모든 지점까지의 최단거리가 아니라 한점으로 도착하는 다른 모든 지점에서 부터의 최단거리가 된다. 

 

#include <vector>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int n, m, x;

int cost[1001];

void dijkstra(int start, vector<vector<pair<int, int>>> &r){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    fill(cost, cost+n+1, 1 << 30);
    pq.push({cost[start] = 0, start});
    while(!pq.empty()){
        auto [costNow, now] = pq.top(); pq.pop();
        if(cost[now] != costNow) continue;
        for(auto [costNext, next] : r[now]){
            if(cost[next] <= cost[now] + costNext) continue;
            cost[next] = cost[now] + costNext; 
            pq.push({cost[next], next});
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    vector<vector<pair<int, int>>> routes(1001);
    vector<vector<pair<int, int>>> reversed(1001);

    cin >> n >> m >> x;
    for(int i=0;i<m;i++){
        int t1, t2, t3;
        cin >> t1 >> t2 >> t3;
        routes[t1].push_back({t3, t2});
        reversed[t2].push_back({t3, t1});
    }

    int ans[n+1];
    int ret = 0;

    dijkstra(x, routes);
    for(int i=1;i<=n;i++){
        ans[i] = cost[i];
    }

    dijkstra(x, reversed);
    for(int i=1;i<=n;i++){
        ret = max(ret, ans[i] + cost[i]);
    }

    cout << ret;
}