[C++] 1238번 파티

 

 

 

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

---

 

25/10/06

 

 

간단한 다익스트라 기초 문제.

---

 

문제 접근 방식:

 

 

$X$에서 시작하는 다익스트라를 돌리고, 역방향 간선들을 담은 그래프에서 $X$에서 시작하는 다익스트라를 돌리면 된다.

 

두 다익스트라를 통해 나온 dist배열의 값들을 더하면 한 지점에서 왕복한 거리가 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 1238번 파티
// 데이크스트라
/*
접근 방법:
정방향 다익 + 역방향 다익
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
typedef long long ll;
#define MAX 1'000'000'000'000LL

struct edge{
    ll node, weight;
    bool operator<(const edge& other) const {
        return weight > other.weight;
    }
};

int main(void){
    int N, M, X; cin >> N >> M >> X;
    vector<vector<edge>> G(N+1);
    vector<vector<edge>> rev_G(N+1);
    ll u, v, w;
    for (int i = 0; i < M; i++){
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        rev_G[v].push_back({u, w});
    }
    vector<ll> dist(N+1, MAX);
    vector<ll> inv_dist(N+1, MAX);
    priority_queue<edge> pq;
    dist[X] = 0;
    pq.push({X, 0});
    while (!pq.empty()){
        ll nowNode = pq.top().node;
        ll totalDistance = pq.top().weight;
        pq.pop();
        if (totalDistance > dist[nowNode]) continue;
        for (edge next: G[nowNode]){
            ll nextNode = next.node;
            ll nextWeight = next.weight;
            if (dist[nowNode] + nextWeight < dist[nextNode]){
                dist[nextNode] = dist[nowNode] + nextWeight;
                pq.push({nextNode, dist[nextNode]});
            }
        }
    }
    inv_dist[X] = 0;
    pq.push({X, 0});
    while (!pq.empty()){
        ll nowNode = pq.top().node;
        ll totalDistance = pq.top().weight;
        pq.pop();
        if (totalDistance > inv_dist[nowNode]) continue;
        for (edge next: rev_G[nowNode]){
            ll nextNode = next.node;
            ll nextWeight = next.weight;
            if (inv_dist[nowNode] + nextWeight < inv_dist[nextNode]){
                inv_dist[nextNode] = inv_dist[nowNode] + nextWeight;
                pq.push({nextNode, inv_dist[nextNode]});
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i < N+1; ++i){
        ans = max(ans, dist[i]+inv_dist[i]);
    }
    cout << ans;
}