1948번: 임계경로

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


$O(n+m)$

DAG 그래프에서 최장거리는 dp를 통해 구할 수 있다.
임의의 dp[i]를 구할 때 참조한 dp[j]에 대해 i->j 간선을 만들어 시작점으로부터 끝점까지 dfs를 통해 지나갈 수 있는 간선 수를 구한다.

#include<cstdio>
#include<vector>
using namespace std;
int dp[10001], ck[10001], n, m, s, e, r;
vector<pair<int, int> > adj[10001];
void dfs1(int h) {
    for (auto it : adj[h]) {
        if (!dp[it.first]) dfs1(it.first);
        if (dp[it.first] + it.second > dp[h]) dp[h] = dp[it.first] + it.second;
    }
}
void dfs2(int h) {
    if (!ck[h]) {
        ck[h] = 1;
        for (auto it : adj[h]) if (dp[it.first] + it.second == dp[h]) dfs2(it.first), r++;
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        adj[x].push_back({ y,z });
    }
    scanf("%d%d", &s, &e);
    dfs1(s);
    dfs2(s);
    printf("%d\n%d", dp[s], r);
    return 0;
}