题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4284
思路：类似于poj3311:http://poj.org/problem?id=3311,首先floyd预处理出两点之间的最短距离，然后就是枚举所有的状态了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 111
#define inf 0x3f3f3f3f int map[MAXN][MAXN];
int dp[<<][];
int city[],cost[],value[];
int N,M,H,money; void floyd()
{
for(int k=;k<=N;k++)
for(int i=;i<=N;i++)
for(int j=;j<=N;j++)
if(map[i][k]<inf&&map[k][j]<inf&&map[i][k]+map[k][j]<map[i][j])
map[i][j]=map[i][k]+map[k][j];
} int main()
{
int _case,u,v,w;
scanf("%d",&_case);
while(_case--){
scanf("%d%d%d",&N,&M,&money);
for(int i=;i<=N;i++)
for(int j=;j<=N;j++)
map[i][j]=(i==j)?:inf;
while(M--){
scanf("%d%d%d",&u,&v,&w);
map[u][v]=map[v][u]=min(map[u][v],w);
}
floyd();
scanf("%d",&H);
for(int i=;i<H;i++){
scanf("%d%d%d",&city[i],&value[i],&cost[i]);
}
memset(dp,-,sizeof(dp));
for(int i=;i<H;i++){
int tmp=money-map[][city[i]]-cost[i];
if(tmp>=)dp[(<<i)][i]=tmp+value[i];
}
for(int state=;state<(<<H);state++){
for(int i=;i<H;i++){
if((state&(<<i))==)continue;
if(dp[state][i]<)continue;
for(int j=;j<H;j++){
if(state&(<<j))continue;
if(map[city[i]][city[j]]==inf)continue;
if(dp[state][i]-map[city[i]][city[j]]-cost[j]<)continue;
dp[state|(<<j)][j]=max(dp[state|(<<j)][j],dp[state][i]-map[city[i]][city[j]]-cost[j]+value[j]);
}
}
}
bool flag=false;
for(int i=;i<H;i++){
if(dp[(<<H)-][i]-map[city[i]][]>=){
flag=true;
break;
}
}
flag?puts("YES"):puts("NO");
}
return ;
}