題目：給出一些城市，從1出發，旅游一圈回到1，由於花費可能不夠，所以選擇一些城市打工，打工之前需要花費d買一個證，工資為c。選中的城市必須去工作一次，而且只能工作一次，問能不能完成旅行
比賽的時候，卡了很久，當時隊友用SPFA+狀態DP+堆棧寫的，主要是把一點考慮錯了
當時把C和D合並了，其實是不對的，因為首先是要購買證，然後才能工作，否則拿不到工資。
也就是先要判斷夠不夠買證的錢D，然後才能拿到工資。
跪舔，先用Floyd預處理最短路n^3，然後狀態DP，h*h*2^h，4S+,效率很低的做法
可以用隊列，堆棧加速
[cpp]
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#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<n;i++){
for(int j=0;j<n;j++)
path[i][j]=inf;
path[i][i]=0;
}
for(int i=0;i<m;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<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;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<h;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<<pos]=money-d[pos]+c[pos];dp[pos][0]=money;
for(int i=0;i<(1<<h);i++){
for(int j=0;j<h;j++){
if(dp[j][i]==-1) continue;
for(int k=0;k<h;k++){
if(k==j||((1<<k)&i)) continue;
//錢夠在兩個城市之間移動，而且夠買證
if(dp[j][i]>=path[work[j]][work[k]]+d[k])
dp[k][i|(1<<k)]=Max(dp[k][i|(1<<k)],dp[j][i]-path[work[j]][work[k]]-d[k]+c[k]);
}
}
}
bool ans=false;
for(int i=0;i<h;i++)
//最後判斷能不能返回起點
if(dp[i][(1<<h)-1]>=path[work[i]][0]){
ans=true;
break;
}
puts(ans?"YES":"NO");
}
return 0;
}
