本文共 1044 字，大约阅读时间需要 3 分钟。

#include
   
    using namespace std;typedef long long ll;const int maxn=5e3+5;const int inf=1e9+1;int pre[maxn][maxn];int dp[maxn][maxn],ru[maxn];vector
    
     
      >g[maxn];void tuopu(int n){
   	queue
      
       q; 	for(int i=1;i<=n;++i) if(ru[i]==0) q.push(i);	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) dp[i][j]=inf;	dp[1][1]=0;	while(!q.empty())	{
   		int top=q.front();		q.pop();		for(auto to:g[top])		{
   			if(ru[to.first])			{
   				ru[to.first]--;				for(int j=2;j<=n;++j)				if(dp[to.first][j]>dp[top][j-1]+to.second) dp[to.first][j]=dp[top][j-1]+to.second,pre[to.first][j]=top;				if(ru[to.first]==0) q.push(to.first);			}		}	}}void dfs(int now,int ans){
   	if(!ans) return ;	dfs(pre[now][ans],ans-1);	printf("%d ",now);}int main(){
   	int n,m,x,y;	ll T,z;	scanf("%d%d%lld",&n,&m,&T);	for(int i=1;i<=m;++i)	{
   		scanf("%d %d %lld",&x,&y,&z);		g[x].push_back({
   y,z});		ru[y]++;	}	tuopu(n);	int ans=0;	for(int i=1;i<=n;++i) if(dp[n][i]<=T) ans=max(ans,i);	printf("%d\n",ans);	dfs(n,ans); }
      
     
    
   

转载地址：http://jeewz.baihongyu.com/