HDU 4284 Travel(12年天津online floyd + tsp状态DP)
参考：http://blog.csdn.net/acm_cxlove/article/details/7963286
tsp的一些讲解：http://blog.csdn.net/gfaiswl/article/details/4749713
floyd + tsp
（1）如果没有点0，将其加入，并设c[],d[]，都为0即可
（2）dp[i][j]表示从0开始经过集合j中的点最后在i点的最大钱数
（3）最后判断，dp[i][ALL]表示遍历了所有的点后，位于i点的最大钱数，则判dp[i][ALL]和dis[num[i]][0]的大小关系即可
#include <cstdio>#include <ctime>#include <cstdlib>#include <cstring>#include <queue>#include <string>#include <set>#include <stack>#include <map>#include <cmath>#include <vector>#include <iostream>#include <algorithm>#include <bitset>using namespace std;//LOOP#define FE(i, a, b) for(int i = (a); i <= (b); ++i)#define FED(i, b, a) for(int i = (b); i>= (a); --i)#define REP(i, N) for(int i = 0; i < (N); ++i)#define CLR(A,value) memset(A,value,sizeof(A))//INPUT#define RI(n) scanf("%d", &n)#define RII(n, m) scanf("%d%d", &n, &m)#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)#define RS(s) scanf("%s", s)typedef long long LL;const int INF = 1000000007;const int MOD = 1000000007;const double eps = 1e-10;const int MAXN = 31000;int ALL;int dis[110][110];int dp[20][1 << 17];int c[20], d[20];int num[20];int n;void floyd(){ REP(k, n) REP(i, n) REP(j, n) { dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); }}int main(){ int m, h; int money; int x, y, z; int T; RI(T); while (T--) { RIII(n, m, money); REP(i, n + 1) REP(j, n + 1) dis[i][j] = i == j ? 0 : INF; while (m--) { RIII(x, y, z); x--; y--; dis[x][y] = min(dis[x][y], z); dis[y][x] = dis[x][y]; } floyd(); int pos = -1; RI(h); REP(i, h) { RIII(num[i], d[i], c[i]); num[i]--; if (num[i] == 0) pos = i; } if (pos == -1) { num[h] = 0; c[h] = 0; d[h] = 0; pos = h++; } ALL = (1 << h) - 1; CLR(dp, -1);/// REP(i, h) if (money - c[i] - dis[num[i]][0] >= 0) dp[i][1 << i] = money - c[i] + d[i] - dis[num[i]][0];// if (money - c[pos] >= 0) dp[pos][1 << pos] = money - c[pos] + d[pos];// dp[pos][0] = money;///初始状态 REP(ss, ALL + 1) REP(i, h) { if (dp[i][ss] == -1) continue; REP(j, h) {// if (i != j && (ss & (1 << j))) continue; if (ss & (1 << j)) continue; if (dp[i][ss] >= dis[num[i]][num[j]] + c[j]) dp[j][ss | (1 << j)] = max(dp[j][ss | (1 << j)], dp[i][ss] - dis[num[i]][num[j]] - c[j] + d[j]); } } int ans = 0; REP(i, h) { if (dp[i][ALL] >= dis[num[i]][0]) { ans = 1; break; } } if (ans) puts("YES"); else puts("NO"); } return 0;}