<>

题目大意：

一个DAG图有n个点，m条边，走过每条边都会花费一定的时间，问你在不超过T时间的条件下，从1到n点最多能够经过几个节点。

解题分析：

对这个有向图，我们进行拓扑排序，并且在拓扑排序的过程中，用dp来进行状态的转移，$dp[i][j]$表示，在以$i$为终点的且经过$j$个点的路径中，所花的最少时间。

#include 
     
      using namespace std;#define pb push_backconst int N = 5e3+5;int dp[N][N],path[N][N],indeg[N];bool vis[N];int n,m,T;struct Edge{ int to,val; };vector
      
       G[N];inline void Toposort(){    queue
       
        q;    memset(dp,0x3f,sizeof(dp));    dp[1][1]=0;    for(int i=1;i<=n;i++) if(!indeg[i]){        vis[i]=true;q.push(i);    }    while(!q.empty()){        int u=q.front();q.pop();        vis[u]=true;        for(int i=0;i
        
         dp[u][j-1]+cost){                        dp[v][j]=dp[u][j-1]+cost;                        path[v][j]=u;      //记录转移到该状态的节点                    }                }            }            if(!indeg[v])q.push(v);        }    }}void Output(int now,int num){      //输出路径    if(now==1){ printf("%d",now);return; }    Output(path[now][num],num-1);    printf(" %d",now);}inline void Print(){    int res=0;    for(int i=n;i>=1;i--){        if(dp[n][i]<=T){ res=i; break; }    }printf("%d\n",res);    if(res)Output(n,res);    puts("");}int main(){    scanf("%d%d%d",&n,&m,&T);    for(int i=1;i<=m;i++){        int u,v,w;scanf("%d%d%d",&u,&v,&w);        G[u].pb(Edge{v,w});        indeg[v]++;    }    Toposort();    Print();}