도망자 원숭이

백준 1602번: 도망자 원숭이

아이디어

현재 최단 거리와 그 경로에 있는 최대 지연 시간을 함께 기록한다. 최단 거리 갱신시 최대 지연 시간까지 합쳐서 계산한다. 이 때 지연시간이 짧은 노드부터 순차적으로 방문해본다. 정렬 후 DP를 하는 느낌으로?

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int INF = 1e9, MAX = 500;
int N, M, Q;
pair<int, int> graph[MAX][MAX]; // cost, max_delay
int max_d[MAX][MAX];
vector<pair<int, int>> delay; // delay, idx

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M >> Q;

    for (int i = 0; i < N; i++) {
        int d;
        cin >> d;
        delay.push_back({d, i});
    }

    while (M--) {
        int a, b, c;
        cin >> a >> b >> c;
        int d = max(delay[a-1].first, delay[b-1].first);
        graph[a-1][b-1] = {c, d};
        graph[b-1][a-1] = {c, d};
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (!graph[i][j].first) {
                graph[i][j] = {INF, max(delay[i].first, delay[j].first)};
            }
        }
    }

    sort(delay.begin(), delay.end());

    for (int k = 0; k < N; k++) {
        int d = delay[k].first;
        int n = delay[k].second;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int md = max(graph[i][j].second, d);
                if (graph[i][j].first+graph[i][j].second > graph[i][n].first+graph[n][j].first+md) {
                    graph[i][j].first = graph[i][n].first+graph[n][j].first;
                    graph[i][j].second = md;
                }
            }
        }
    }

    while (Q--) {
        int s, t;
        cin >> s >> t;
        if (graph[s-1][t-1].first == INF) cout << -1 << '\n';
        else cout << graph[s-1][t-1].first+graph[s-1][t-1].second << '\n';
    }

    return 0;
}

여담

어려웡,, 푼사람들 보니까 그냥 다익스트라 N번 돌린 사람도 있었다.