这题很容易想到状压的记忆化搜索
f[i][j][k]表示到第i个点 拿物品的状态 送到物品的状态
然后就可以愉快地dfs了
结果MLE。。
1024*1024*20爆了
那怎么办。。。。。
反正对于一种物品只有三种状态
那不如使用三进制状压。。。。
算了一下空间复杂度过得去
于是就A了
一开始还因为误以为双向边WA了几发。。
#include<cstdio> #include<cstdlib> #include<cstring> const int N=21; int n,m,q; int g[N][N]; int s[N],t[N],l[N],r[N]; int f[N][59050*3]; int bin[11]; int ans=0; int mymax (int x,int y){return x>y?x:y;} int mymin (int x,int y){return x<y?x:y;} int get (int x) { int tt=0; for (int u=10;u>=0;u--) { if (x>=bin[u]*2) tt++; while (x>=bin[u]) x-=bin[u]; } return tt; } int check (int x,int y)//x的第y位是什么 { // printf("%d %d\n",x,y); for (int u=10;u>y;u--) while (x>=bin[u]) x=x-bin[u]; if (x>=bin[y]*2) return 2; if (x>=bin[y]) return 1; return 0; } int xx=0; void dfs (int now,int x,int z)//现在在哪一个点 物品的状态 现在过了多少时间 { /* printf("%d %d\n",now,z); system("pause");*/ for (int u=1;u<=q;u++) { if (s[u]==now&&check(x,u)==0&&z>=l[u])//这里可以取 x=x+bin[u]; if (t[u]==now&&check(x,u)==1&&z<=r[u]) x=x+bin[u]; } if (f[now][x]<=z) return ; f[now][x]=z; ans=mymax(ans,get(x)); if (z>=xx) return ; if (ans>=q) return ; for (int u=1;u<=q;u++) { if (z+g[now][t[u]]>r[u]) continue; if (check(x,u)==0) dfs(s[u],x,mymax(z+g[now][s[u]],l[u])); if (check(x,u)==1) dfs(t[u],x,z+g[now][t[u]]); } } int main() { bin[0]=1;for (int u=1;u<=10;u++) bin[u]=bin[u-1]*3; // printf("%d\n",bin[10]); memset(f,127,sizeof(f)); memset(g,63,sizeof(g)); scanf("%d%d%d",&n,&m,&q); for (int u=1;u<=n;u++) g[u][u]=0; for (int u=1;u<=m;u++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); g[x][y]=mymin(g[x][y],z); } for (int k=1;k<=n;k++) for (int u=1;u<=n;u++) for (int i=1;i<=n;i++) g[u][i]=mymin(g[u][i],g[u][k]+g[k][i]); for (int u=1;u<=q;u++) { scanf("%d%d%d%d",&s[u],&t[u],&l[u],&r[u]); xx=mymax(xx,r[u]); } dfs(1,0,0); printf("%d\n",ans); return 0; }