임계경로

백준 1948번: 임계경로

아이디어

시작 노드부터 위상 정렬을 하면서 각 노드에 진입하는데 가장 오래 걸리는 시간을 기록한다. 이후 종료 노드에서 역방향 간선을 타면서 간선의 비용이 현재 노드 최대 진입 비용 - 다음 노드 최대 진입 비용 인 경우가 얼마나 되는지 센다.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 10001;
int N, M, S, E;
vector<pair<int, int>> adj[MAX], reverse_adj[MAX];
int indegree[MAX], last[MAX];
bool visited[MAX][MAX];

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

    cin >> N >> M;
    while (M--) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        reverse_adj[b].push_back({a, c});
        indegree[b]++;
    }
    cin >> S >> E;

    queue<int> q;
    q.push(S);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto p : adj[cur]) {
            int next = p.first;
            int cost = last[cur]+p.second;
            last[next] = max(last[next], cost);
            if (!--indegree[next]) q.push(next);
        }
    }

    int ans = 0;
    q.push(E);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto p : reverse_adj[cur]) {
            int next = p.first;
            int nc = p.second;
            if (!visited[cur][next] && last[cur]-last[next] == nc) {
                visited[cur][next] = true;
                q.push(next);
                ans++;
            }
        }
    }

    cout << last[E] << '\n' << ans << '\n';
    
    return 0;
}

여담

소공 시간에 배운다는 소문이..