1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| #include<bits/stdc++.h> using namespace std; #define rep(i,a,n) for(int i=(a);i<(n);i++) #define per(i,a,n) for(int i=(n);i>=(a);i--) #define fi first #define se second typedef pair <int,int> pII; typedef long long ll; const int INF = 0x3f3f3f3f;
const int maxn = 5e3+10; int n,m,T,cnt; int head[maxn],vis[maxn]; struct node{ int to,next; ll val; }G[maxn]; void init(){ memset(head,-1,sizeof(head)); cnt = 1; } void addedge(int u,int v,int val){ G[cnt].to = v; G[cnt].val = val; G[cnt].next = head[u]; head[u] = cnt++; } int dp[maxn][maxn], bef[maxn][maxn]; void dfs(int u){ vis[u] = 1; if(u==n) return; for(int i=head[u];~i;i=G[i].next){ int v = G[i].to; if(vis[v]==0) dfs(v); rep(j,1,n){ if(dp[v][j] + G[i].val < dp[u][j+1]){ dp[u][j+1] = dp[v][j] + G[i].val; bef[u][j+1] = v; } } } } int main(){ #ifdef LOCAL freopen("1.in","r",stdin); #endif scanf("%d%d%d",&n,&m,&T); init(); memset(dp,0x3f,sizeof(dp)); rep(i,1,m+1){ int u,v,val; scanf("%d%d%d",&u,&v,&val); addedge(u,v,val); } dp[n][1] = 0; dfs(1); int idx = 1; per(i,1,n+1){ if(dp[1][i] <= T){ printf("%d\n",i); idx = i; break; } } printf("1 "); int cnt = 1; while(idx > 1){ printf("%d ",bef[cnt][idx]); cnt = bef[cnt][idx--]; } return 0; }
|