本文共 1590 字，大约阅读时间需要 5 分钟。
给定一张图，问从1到n代价不超过T，最多不重复的经过多少个点，图是DAG。
DAG想到d[i][j]表示到i点的时候已经经过j个点的时候经过的点。
如果只是想到dp状态表示限制可能想不到，此题是把限制表示在key-value的value中。
contest的时候一遍过没想太多，重测的时候wa了，一组数据没有到达n点。后来发现是因为终点一定要到n但是我在记忆化搜索的时候没有限制j到0的时候返回INF，如果不想在dfs的时候限制，初态也应该初始化到d[0]数组，不是d[1]。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define FORD(i,k,n) for(int i=n;i>=k;i--)#define FOR(i,k,n) for(int i=k;i<=n;i++)#define CLR(a,b) memset(a,b,sizeof(a));#define INF 0x3f3f3f3f#define LLINF 0x3f3f3f3f3f3f3f3f#define ll long long#define LL long long#define ull unsigned long long#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define ptb(b,a){int tmp=a;string s;do{s+=tmp%2+'0';tmp/=2;}while(tmp);reverse(s.begin(),s.end());cout<<"bin "<<<"="<< e[maxn];int d[maxn][maxn];int f[maxn][maxn];void read(){ FOR(i,1,n) e[i].clear(); FOR(i,1,m) { int u,v,w; cin>>u>>v>>w; edge tmp; tmp.v=v;tmp.w=w; e[u].push_back(tmp); }}void preprocess(){ FOR(i,0,n) FOR(j,0,n) d[i][j]=-1; FOR(i,0,n) d[n][i]=-1; d[n][1]=0;}int dfs(int i,int j){ if(d[i][j]!=-1) return d[i][j]; else if(j==0) return INF;//这句没有写 else { int sz=e[i].size(); d[i][j]=INF; FOR(_,0,sz-1) { int k=e[i][_].v,w=e[i][_].w; ll tmp=d[k][j-1]+w; if(tmp>T) { continue; } else if(dfs(k,j-1)!=INF&&(d[k][j-1]+w) >n>>m>>T; read(); preprocess(); solve(); return 0;}
转载于:https://www.cnblogs.com/diang/p/5933843.html
