Codeforces 721C Journey（DAG上dp）

传送门

题意：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;
}