传送门
题意：n个点m条边的有向无环图，每走一条边消耗一定时间，问从1走到n，消耗时间不超过T的情况下最多经过多少个点
题解：由于n，m范围不大所以对于这个DAG可以做的dp，定义f[i][j]表示走到i点，经过了j个点消耗时间的最小值，顺便开个pre数组记录一下转移路径。
说一下坑点，首先这个题卡空间，边权和f数组都不能是longlong。而且1不一定是DAG入度为0的点，也就是说1不一定能走到所有点。所以要先将1不能走到的点的出边贡献给别的点的入度减掉，否则拓扑排序时有可能有些点入度始终无法为0导致不入队。
天坑数据：
4 4 10 2 1 1 2 3 1 1 3 1 3 4 1 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int N=5e3+4; const ll INF=0x3f3f3f3f; int n,m,T; struct Edge { int v,w,nxt; }e[N]; int head[N],etot; int f[N][N];//arriving at i, the mininum time used to visit j points int pre[N][N]; int deg[N],pd[N]; bool vis[N],inq[N]; inline int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } inline void adde(int u,int v,int w) { e[++etot].nxt=head[u],e[etot].v=v,e[etot].w=w,head[u]=etot; } queue<int> q; inline void smin(int &x,int y) { x=x<y?x:y; } inline void cut(int source) { memset(vis,false,sizeof(vis)); for (int i=1;i<=n;++i) pd[i]=deg[i]; q.push(source); f[source][1]=0; vis[source]=true; while (!q.empty()) { int p=q.front(); q.pop(); for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; if (!vis[v]) { vis[v]=true; q.push(v); } } } for (int p=1;p<=n;++p) if (!vis[p]) { for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; --deg[v]; } } } inline void topo(int source) { memset(pre,-1,sizeof(pre)); memset(f,INF,sizeof(f)); q.push(source); f[source][1]=0; while (!q.empty()) { int p=q.front(); q.pop(); for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; --deg[v]; for (int j=2;j<=n;++j) if (f[p][j-1]<T&&(ll)f[v][j]>(ll)f[p][j-1]+e[i].w) { f[v][j]=f[p][j-1]+e[i].w; pre[v][j]=p; } if (!deg[v]) q.push(v); } } } int s[N],tot; int main() { // printf("memory:%d\n",sizeof(f)*2+sizeof(e)*2); memset(head,-1,sizeof(head)); n=read(),m=read(),T=read(); for (int i=0;i<m;++i) { int u=read(),v=read(),w=read(); adde(u,v,w); ++deg[v]; } cut(1); topo(1); int ans; for (int i=n;i;--i) if (f[n][i]<=T) { ans=i; break; } int cur=n,temp=ans; while (~cur) { s[++tot]=cur; cur=pre[cur][temp]; --temp; } printf("%d\n",ans); for (int i=tot;i;--i) printf("%d ",s[i]); return 0; }
