HDU 4284 Travel(12年天津状态DP)

题目：给出一些城市，从1出发，旅游一圈回到1，由于花费可能不够，所以选择一些城市打工，打工之前需要花费d买一个证，工资为c。选中的城市必须去工作一次，而且只能工作一次，问能不能完成旅行

比赛的时候，卡了很久，当时队友用SPFA+状态DP+堆栈写的，主要是把一点考虑错了

当时把C和D合并了，其实是不对的，因为首先是要购买证，然后才能工作，否则拿不到工资。

也就是先要判断够不够买证的钱D，然后才能拿到工资。

跪舔，先用Floyd预处理最短路n^3，然后状态DP，h*h*2^h，4S+,效率很低的做法

可以用队列，堆栈加速

[cpp]
#include
#include
#include
#include
#define inf 1<<28
#define N 105
#define Min(a,b) ((a)<(b) (a):(b))
#define Max(a,b) ((a)>(b) (a):(b))
using namespace std;
int n,m,money,h;
int path[N][N];
int dp[20][1<<16];
int work[20],c[20],d[20];
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&money);
for(int i=0;i for(int j=0;j path[i][j]=inf;
path[i][i]=0;
}
for(int i=0;i int u,v,w;
scanf("%d%d%d",&u,&v,&w);
u--;v--;
path[u][v]=Min(path[u][v],w);
path[v][u]=path[u][v];
}
//Floyd预处理
for(int k=0;k for(int i=0;i for(int j=0;j if(i!=k&&i!=j&&j!=k)
path[i][j]=Min(path[i][k]+path[k][j],path[i][j]);
scanf("%d",&h);
int pos=-1;
for(int i=0;i scanf("%d%d%d",&work[i],&c[i],&d[i]);
work[i]--;
if(work[i]==0) pos=i; //说明必需点中包含了起点1
}
//如果不包含，我们加入冗余点，便于后面处理，c和d都为0
if(pos==-1){
work[h]=0;c[h]=0;d[h]=0;
pos=h++;
}
memset(dp,-1,sizeof(dp));
if(money-d[pos]>=0) dp[pos][1< for(int i=0;i<(1< for(int j=0;j if(dp[j][i]==-1) continue;
for(int k=0;k if(k==j||((1< //钱够在两个城市之间移动，而且够买证
if(dp[j][i]>=path[work[j]][work[k]]+d[k])
dp[k][i|(1< }
}
}
bool ans=false;
for(int i=0;i //最后判断能不能返回起点
if(dp[i][(1<=path[work[i]][0]){
ans=true;
break;
}
puts(ans "YES":"NO");
}
return 0;
}

HDU 4284 Travel(12年天津 状态DP)