题意：

给定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<stdio.h>

#include<string.h>

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

#include<vector>

#include<queue>

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(){

	queue<node>q;

	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<top;i++){

			scanf("%d %d %d",&Stack[i],&C[i],&D[i]);

			go[Stack[i]] = 1<<i;

		}

		BFS();

		int ans = -1;

		for(i = 0; i < top; i++)

			ans = max(dp[i][(1<<top)-1] - dis[1][Stack[i]], ans);

		ans>=0?puts("YES"):puts("NO");

	}

	return 0;

}

/*

2 1 1

1 2 1

2

1 100 1

2 1 0

*/