【模板】DAG最长路

#include<bits/stdc++.h>
using namespace std;
int dp[100010],nnext[1000010];
int n,m,t;
vector<int>g[100010];
vector<int>c[100010];
bool vis[1000010];
int DAG(int x)
{
    if(dp[x])return dp[x];
    int to,temp;
    for(int i=0;i<g[x].size();i++)
    {
        to=g[x][i];
        temp=DAG(to);
        if(dp[x]<temp+c[x][i])
        {
            dp[x]=temp+c[x][i];
            nnext[x]=to;
        }
    }
    return dp[x];
}
int DAG_to(int x)//有指向DAG
{
    if(vis[x])return dp[x];
    int to,temp;
    for(int i=0;i<g[x].size();i++)
    {
        to=g[x][i];
        temp=DAG_to(to);
        if(dp[x]<temp+c[x][i])
        {
            dp[x]=temp+c[x][i];
            nnext[x]=to;
        }
    }
    return dp[x];
}
void print(int x)
{
    int at=x;
    while(nnext[at])
    {
        cout<<at<<"->";
        at=nnext[at];
    }
    cout<<at<<endl;
}
int main()
{
    cin>>n>>m>>t;
    int a,b,cost;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>cost;
        g[a].push_back(b);
        c[a].push_back(cost);
    }
    memset(dp,128,sizeof dp);
    dp[12]=0;
    DAG_to(1);
    for(int i=1;i<=n;i++)
    cout<<i<<"->"<<dp[i]<<endl;
    print(1);
}
/*
15 21 12
1 2 10
1 3 15
1 4 16
2 16 25
4 16 25
3 5 10
4 5 12
16 6 7
5 7 12
5 8 10
5 9 9
6 10 11
7 11 12
8 12 12
8 13 10
9 14 9
10 15 12
11 15 15
12 15 14
13 15 13
14 15 16
*/