題意：
給定n個點 m條無向邊 d元。
下面m行表示每條邊 u<=>v 以及花費 w
下面top
下面top行
num c d 表示點標為num的城市 工資為c 健康證價格為d
目標是經過給定的top個城市，當到達該城市時，必須馬上購買該城市的健康證並打工賺錢（每個城市只打工1次）
問從1城市出發，最後回到1城市，能否收集到所有的健康證
思路：
由於top很小，所以狀壓dp
dp[i][tmp]表示當前處於i點 經過城市的狀態為tmp時 身上最多的錢。
首先對dis數組floyd 跑出最短路，然後裸裸地轉移。
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll int
#define inf 100000000
#define N 101
int dp[15][1<<15];
int go[N];
int n, m, d;
int dis[N][N];
int C[N], D[N];
int Stack[N], top;
void floyd(){
for(int z = 1; z <= n; z++)dis[z][z] = 0;
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)if(dis[i][k] !=inf && i!=k)
for(int j = 1; j <= n; j++)if(dis[k][j]!=inf && j!=i && j!=k)
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
}
void init(){
memset(dp, -1, sizeof dp);
for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)dis[i][j] = inf;
}
struct node{
int u, t, mon;
node(int a=0,int b=0,int c=0):u(a),t(b),mon(c){}
};
void BFS(){
queueq;
for(int i = 0; i < top; i++) if(d - dis[1][Stack[i]] - D[i]>=0)
q.push(node(Stack[i], go[Stack[i]], d-dis[1][Stack[i]]-D[i]+C[i]));
while(!q.empty())
{
node a = q.front(); q.pop();
for(int i = 0; i < top; i++){
int v = Stack[i];
if(a.t & go[v])continue;
node now = a; now.t |= go[v];
if(dp[i][now.t]==-1 && now.mon - dis[a.u][v] - D[i] >= 0)
{
now.mon = now.mon - dis[a.u][v] - D[i] + C[i];
dp[i][now.t] = now.mon;
q.push(now);
}
}
}
}
int main()
{
int i, T, j, u, v, dd;scanf("%d",&T);
while(T--){
scanf("%d %d %d",&n,&m,&d);
init();
while(m--){
scanf("%d %d %d",&u,&v,&dd);
dis[u][v] = dis[v][u] = min(dis[u][v],dd);
}
floyd();
scanf("%d",&top);
for(i=0;i=0?puts("YES"):puts("NO");
}
return 0;
}
/*
2 1 1
1 2 1
2
1 100 1
2 1 0
*/
