2611번: 자동차경주

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


$O(n+m)$

DAG 그래프이므로 dp로 해결할 수 있다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 1000;
int n, m, dp[MXN + 1], go[MXN + 1];
vector<pair<int, int> > adj[MXN + 1];
int f(int h) {
    if (!dp[h] && h != 1) for (auto it : adj[h]) {
        int t = f(it.first) + it.second;
        if (t > dp[h]) dp[h] = t, go[h] = it.first;
    }
    return dp[h];
}
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 });
    int r = 0, idx = 1, t;
    for (auto it : adj[1]) {
        t = f(it.first) + it.second;
        if (t > r) r = t, idx = it.first;
    }
    printf("%d\n1", r);
    for (int i = idx; i; i = go[i]) printf(" %d", i);
    return 0;
}