摘要：题意：给一个无环的图,问用不超过T的时间从1到n最多可以经过多少个点。要求输出一条路径。思路：因为无环，可以用DP做。不过因为时间最短的原因要拓扑排序后再DP，目测由底向上的更新也是可以的。const oo=1100000000; var dp,f:array[1..5000,1..5000]of longint; he
题意：给一个无环的图,问用不超过T的时间从1到n最多可以经过多少个点。要求输出一条路径。
思路：因为无环，可以用DP做。不过因为时间最短的原因要拓扑排序后再DP，目测由底向上的更新也是可以的。
const oo=1100000000;
var dp,f:array[1..5000,1..5000]of longint;
head,vet,next,len,flag,d,q,b:array[1..11000]of longint;
n,m,tot,i,j,time,k,x,y,z,ans:longint;
procedure add(a,b,c:longint);
begin
inc(tot);
next[tot]:=head[a];
vet[tot]:=b;
len[tot]:=c;
head[a]:=tot;
end;
procedure print(k,m:longint);
begin
if m=1 then begin write(k); exit; end;
print(f[k,m],m-1);
write(' ',k);
end;
procedure topsort;
var t,w,i,e,v,u:longint;
begin
fillchar(b,sizeof(b),0);
t:=0; w:=0;
for i:=1 to n do
if d[i]=0 then begin inc(w); q[w]:=i; b[i]:=1; end;
while t<w do
begin
inc(t); u:=q[t];
e:=head[u];
while e<>0 do
begin
v:=vet[e];
for i:=1 to n-1 do
if dp[u,i]+len[e]<dp[v,i+1] then
begin
dp[v,i+1]:=dp[u,i]+len[e];
f[v,i+1]:=u;
end;
dec(d[v]);
e:=next[e];
end;
for i:=1 to n do
if (d[i]=0)and(b[i]=0) then begin inc(w); q[w]:=i; b[i]:=1; end;
end;
end;
begin
//assign(input,'721C.in'); reset(input);
//assign(output,'721C.out'); rewrite(output);
readln(n,m,time);
for i:=1 to m do
begin
readln(x,y,z);
add(x,y,z);
inc(d[y]);
end;
for i:=1 to n do
for j:=1 to n do dp[i,j]:=oo;
dp[1,1]:=0;
topsort;
for i:=n downto 1 do
if dp[n,i]<=time then begin ans:=i; break; end;
writeln(ans);
print(n,ans);
//close(input);
//close(output);
end.
