백준[1238] 파티

문제 설명

문제 링크

http://icpc.me/1238

1238번: 파티

풀이

다익스트라를 이용하여 풀 수 있다.

모든 점에 대해서 다익스트라를 돌려서 O(M^2logN)에도 풀 수 있지만, 관점을 약간 틀면 더 O(MlogN)에 풀 수 있다.

단방향 도로이기 때문에 순방향으로 x를 시작점으로 돌린다면 마을로 돌아가는 최간거리를 구할 수 있다.

그리고 역방향그래프를 x를 시작점으로 돌린다면 x까지 가는 최단거리를 구할 수 있다.

코드

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

const int N = 1003;
const int INF = 1e8;
vector<pii> adj1[N];
vector<pii> adj2[N];
int n, m, x; 
int dist1[N];
int dist2[N];

void dijkstra(vector<pii> v[], int dist[]) {
    priority_queue<pii, vector<pii>, greater<>> pq;
    fill(dist, dist + N, INF);
    pq.push({0, x});
    dist[x] = 0;
    while (!pq.empty()) {
        int cur = pq.top().second;
        pq.pop();
        for (auto [nxt, d] : v[cur]) {
            if (dist[cur] + d < dist[nxt]) {
                dist[nxt] = dist[cur] + d;
                pq.push({dist[nxt], nxt});
            }
        }
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &x);
    for (int i = 0; i < m; i++) {
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        adj1[a].push_back({b, c});
        adj2[b].push_back({a, c});
    }
    dijkstra(adj1, dist1);
    dijkstra(adj2, dist2);      
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dist1[i] + dist2[i]);
    printf("%d", ans);
}