백준 1238 / C++

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

1238번: 파티

 

[ 풀이 ]

 

다익스트라+가벼운 발상을 필요로 하는 문제이다.

파티장에서 집으로 최단거리는 다익 1번으로 구해진다.

그런데 집에서 파티장까지 N개는 다익스트라 N번을 해야할까?

그렇게해도 시간안엔 풀리지만 다익 1번에 구할 수 있다.

역방향 그래프도 만든후에 파티장에서 다시 다익을 돌려주면 끝. 

 

 

[ 코드 ] 

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int>pi;
int n, m, pt, a, b, c;
vector<pi> g[10001], revg[10001];
int dist[10001][2];

// 그래프 G , 시작점 st에서 다익스트라 
void dijk(vector<pi> G[], int i, int st) {
    priority_queue<pi, vector<pi>, greater<pi>> pq;
    for (int x = 1; x <= n; x++) {
        dist[x][i] = 1e9;
    }
    dist[st][i] = 0;
    pq.push({ 0, st });
    while (pq.size()) {
        int d, x;
        tie(d, x) = pq.top(); pq.pop();
        if (dist[x][i] != d) continue;
        for (auto nxt : G[x]) {
            int nx = nxt.first;
            int w = nxt.second;
            if (dist[nx][i] > dist[x][i] + w) {
                dist[nx][i] = dist[x][i] + w;
                pq.push({ dist[nx][i], nx });
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> pt;
    while (m--) {
        cin >> a >> b >> c;
        g[a].push_back({ b,c });
        revg[b].push_back({ a, c });
    }
    dijk(g, 0, pt); // 파티 -> 집
    dijk(revg, 1, pt); // 집 -> 파티
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        // 최댓값 갱신 
        ans = max(ans, dist[i][0] + dist[i][1]);
    }
    cout << ans << '\n';
}