[BOJ] 파티

[BOJ] 파티

Problem URL : 파티

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define p pair<int,int>
#define INF 987654321
using namespace std;

int n, m, x;
int dist[1001][2];

void dijkstra(vector<p> v[], int dir) {
    priority_queue<p, vector<p>, greater<p> > pq;
    pq.push({ 0, x });
    dist[x][dir] = 0;
    while (!pq.empty()) {
        int hereCost = pq.top().first;
        int here = pq.top().second;
        pq.pop();
        if (dist[here][dir] < hereCost) continue;
        for (const auto edge : v[here]) {
            int nextCost = hereCost + edge.first;
            int next = edge.second;
            if (dist[next][dir] > nextCost) {
                dist[next][dir] = nextCost;
                pq.push({ nextCost, next });
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> x;
    vector<p> a[1001], b[1001];
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back({ w, v });
        b[v].push_back({ w, u });
    }
    fill(&dist[1][0], &dist[n][2], INF);

    dijkstra(a, 0);
    dijkstra(b, 1);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int tmp = dist[i][0] + dist[i][1];
        if (ans < tmp) ans = tmp;
    }
    cout << ans << '\n';
    return 0;
}

Comments

각각의 노드에서 x까지 왕복하는 최솟값을 구하는 문제이다.
x에서 출발해서 각각의 노드까지 가는 것은 x를 출발점으로 하는 일반적인 다익스트라 문제이다.
문제는 각 노드에서 x까지 가는 것인데, 그래프 간선들의 방향을 반대방향으로 뒤집어주면 된다.
그러면 반대로 뒤집어서 만들어진 인접 리스트로 x에서 각 노드까지 다익스트라를 적용하는 것으로 생각할 수 있다.