백준 1948번: 임계경로 - 위상정렬 C++

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

1948번: 임계경로

#include <bits/stdc++.h>
using namespace std;

int n, m;

vector<pair<int,int> > adj[10001];
vector<pair<int, int> > rev_adj[10001];
int redegree[10001];
int rev_res[10001];

int degree[10001];
int res[10001];

bool vis[10001];

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

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b,c;
        cin >> a >> b >> c;

        adj[a].push_back({ b,c });
        rev_adj[b].push_back({ a,c });
        redegree[a]++;
        degree[b]++;
    }

    queue<int> Q;

    int s, e;
	cin >> s >> e;
    Q.push(s);

    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();

        for (auto i : adj[x]) {
            int nx = i.first;
            int nd = i.second;
            res[nx] = max(res[nx], res[x] + nd);

            if (--degree[nx] == 0) {
                Q.push(nx);
            }
        }
    }

    int ans = res[e];
    cout << res[e] << '\n';


    Q.push(e);

    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();

        for (auto i : rev_adj[x]) {
            int nx = i.first;
            int nd = i.second;
            rev_res[nx] = max(rev_res[nx], rev_res[x] + nd);

            if (--redegree[nx] == 0) {
                Q.push(nx);
            }
        }
    }

    set<pair<int, int> > Set;
    Q.push(s);
    vis[s] = 1;
    while (!Q.empty()) {
        int x = Q.front(); Q.pop();

        for (auto i : adj[x]) {
            int nx = i.first;
            int d = i.second;
            if ((res[nx] == res[x] + d) && (res[nx] + rev_res[nx] == ans)) {
                if (!vis[nx]) {
					Q.push(nx);
                    vis[nx] = 1;
                }
                Set.insert({ x,nx });
            }
        }
    }

    cout << Set.size() << '\n';


    return 0;
}

백준 1948번 임계경로