未完待续
#pragma warning(disable:4996) #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include<algorithm> using namespace std; const int INF = 0x3f3f3f3f; const int MAX = (1 << 16) + 10; int n, m, money, h; int s[20], c[20], d[20]; int dp[MAX][20], dist[110][110]; int main() { freopen("in.txt", "r", stdin); int T; scanf("%d", &T); while (T--) { int u, v, w; scanf("%d%d%d", &n, &m, &money); for (int i = 0; i <=n; ++i) { for (int j = i + 1; j <= n; ++j) dist[i][j] = dist[j][i] = INF; } for (int i = 0; i<m; ++i) { scanf("%d%d%d", &u, &v, &w); dist[u][v] = dist[v][u] = min(dist[u][v], w); } scanf("%d", &h); for (int i = 1; i <= h; ++i) { scanf("%d%d%d", &s[i], &c[i], &d[i]); } for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } s[0] = 1, c[0] = d[0] = 0; int bit = 1 << (h + 1); memset(dp, -1, sizeof dp); dp[1][0] = money; for (int i = 1; i<bit; ++i) { for (int j = 0; j <= h; ++j) { for (int k = 1; k <= h; ++k) { if (dp[i][j]<dist[s[j]][s[k]] + d[k]) continue; int p = 1 << k, w = c[k] - d[k]; if (i&p) continue; dp[i | p][k] = max(dp[i | p][k], dp[i][j] - dist[s[j]][s[k]] + w); } } } bool flag = false; for (int i = 0; i <= h; ++i) if (dp[bit - 1][i] - dist[s[i]][1] >= 0) flag = true; if (flag) printf("YES\n"); else printf("NO\n"); } return 0; }