백준 1238 파티

다익스트라 알고리즘은 한 정점에서 나머지 정점들까지의 최단거리를 구하는 알고리즘이다.
이를 응용하면 그래프를 역방향으로 저장할 경우 나머지 정점들에서 한 정점으로의 최단거리를 구할 수 있다.

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int n, m, x;
vector<pii> graph[2][1001];
vector<vector<int>> dist(2, vector<int>(1001));

void dijkstra() {
    for (int i = 0; i < 2; ++i) {
        for (int j = 1; j <= n; ++j) {
            dist[i][j] = 1e9;
        }
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        dist[i][x] = 0;
        pq.push({0, x});
        while (pq.size()) {
            int cost = pq.top().first;
            int now = pq.top().second;
            pq.pop();
            if (dist[i][now] < cost) continue;
            for (int j = 0; j < graph[i][now].size(); ++j) {
                int next = graph[i][now][j].first;
                int nextCost = cost + graph[i][now][j].second;
                if (dist[i][next] > nextCost) {
                    dist[i][next] = nextCost;
                    pq.push({nextCost, next});
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, dist[0][i] + dist[1][i]);
    }
    cout << ans;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m >> x;
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[0][a].push_back({b, c});
        graph[1][b].push_back({a, c});
    }
    dijkstra();
}