原题链接
这题因为要求满足 t 时间内，所以用 dp ，不过我们的状态比较特殊，\(dp[i][j]\) 表示到 \(i\) 点时经过 \(j\) 个点的最短时间，因为题目为 DAG 所以要用拓扑排序，每到一个点，枚举所有出边，更新出点的状态 \(f[v][j+1]=min(f[v][j+1],f[u][j])\)，最后的答案就是所有 \(f[t][j]\le t\) 中最大的 \(j\)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 5005int n,m;
ll t;
int cnt=0;
struct Edge{int to,next,w;
}edge[2*N];
int head[N];void add_edge(int u,int v,int w){cnt++;edge[cnt].to=v;edge[cnt].next=head[u];edge[cnt].w=w;head[u]=cnt;
} int in[N];
queue<int> q;
ll f[N][N];void topo_sort(){for(int i=1;i<=n;i++){if(!in[i]){q.push(i);}}while(!q.empty()){int x=q.front();q.pop();for(int i=head[x];i!=-1;i=edge[i].next){int y=edge[i].to;for(int j=1;j<=n;j++){ll kk=f[x][j]+edge[i].w;if(kk<=t){//直接不加超过t的，其实加也行f[y][j+1]=min(f[y][j+1],kk);}}if(--in[y]==0){q.push(y);}}}
}int main(){ios::sync_with_stdio(false);cin>>n>>m>>t;for(int i=1;i<=n;i++){head[i]=-1;} for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add_edge(u,v,w);in[v]++;}memset(f,0x3f,sizeof f);f[1][1]=0; topo_sort();for(int j=n;j>=1;j--){if(f[n][j]<=t){cout<<j;return 0;}} cout<<0;return 0;
}
