[BOJ] 1948 임계경로

문제

1948번: 임계경로

월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다.

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

풀이

코드

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

struct info {
    int e, cost;
};

int n, m, st, en, total = 0;
int inDegree[10000];
int cost[10000];
vector<int> ans[10000];
int vis[10000];
vector<info> v[10000];

void go() {
    queue<int> q;
    q.push(st);
    for(int i = 0; i < n; i++) {
        int t = q.front(); q.pop();
        for(auto j : v[t]) {
            if (cost[j.e] < cost[t] + j.cost) {
                ans[j.e].clear();
                ans[j.e].push_back(t);
            } else if (cost[j.e] == cost[t] + j.cost) ans[j.e].push_back(t);
            cost[j.e] = max(cost[j.e], cost[t] + j.cost);
            if (--inDegree[j.e] == 0) q.push(j.e);
        }
    }
}

void chk(int t) {
    if (vis[t]) return;
    vis[t] = 1;
    for(int i : ans[t]) {
        total++;
        chk(i);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for(int a, b, c, i = 0; i < m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        a--; b--;
        v[a].push_back({b,c});
        inDegree[b]++;
    }
    scanf("%d %d", &st, &en); st--; en--;
    go();
    chk(en);

    printf("%d\n%d", cost[en], total);
}