[백준 / C++] 1238 - 파티

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

1238번: 파티

파티하는 집 x가 주어졌을때 각 집에서 x로 갔다오는 최단거리를 모두 구하고 그 중 최대값을 묻는 문제이다. 한 정점으로부터 모든 정점으로의 최단거리를 구하는 다익스트라를 이용하면 된다. 하지만 주의할 점으로 여기서는 i에서 x로 가고 x에서 i로 가는 두 방향에 대해서 최단거리를 구해야 한다는 것이다.

 

여기서 문제를 조금 바꿔 해석하면 쉽게 되는데 우선, x에서 모든 정점으로 가는 최단거리를 다익스트라로 한 번 구한다. 그리고 간선의 방향을 바꾼 graph를 저장한 후 이를 이용한 다익스트라를 한번 더 사용한다. 그렇게 되면 1번째는 x에서 모든 정점 2번째는 모든 정점에서 x로 향하는 최단거리를 2번의 다익스트라로 구할 수 있게 된다.

 

문제풀이로 넘어가면 x에서 모든 정점으로 가는 경우를 k = 0인 경우, 모든 정점에서 x로 가는 경우를 k = 1인 경우로 나눈 후, 다익스트라를 2번 진행한다. 여기서 graph[0] 에는 정상적으로 입력을 받고 graph[1] 에는 반대 방향으로 입력한다. 그 후 priority queue를 이용한 다익스트라를 k = 0, 1인 경우에 대해 진행한 후 두 dist를 더한 값 중 최대값을 출력한다.

#include <iostream>
#include <vector>
#include <queue>
#define MAX 1001
#define INF 100000000
#define pii pair<int, int>
using namespace std;

vector<pii> graph[2][MAX];
vector<int> dist[2];
int n, m, x, u, v, t, ans;

void Dijkstra (int k) {
    priority_queue<pii> pq;
    pq.push({0, x});
    dist[k][x] = 0;

    while(!pq.empty()) {
        int now_dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();

        for (auto i : graph[k][now]) {
            int next_dist = i.first + now_dist;
            int next = i.second;

            if (next_dist < dist[k][next]) {
                dist[k][next] = next_dist;
                pq.push({-next_dist, next});
            }
        }
    }
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> x;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> t;
        graph[0][u].emplace_back(t, v);
        graph[1][v].emplace_back(t, u);
    }
    dist[0].resize(n + 1, INF);
    dist[1].resize(n + 1, INF);

    Dijkstra(0);
    Dijkstra(1);

    ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dist[0][i] + dist[1][i]);

    cout << ans << "\n";
    return 0;

}