http://acm.hdu.edu.cn/showproblem.php?pid=4284
2 4 5 10 1 2 1 2 3 2 1 3 2 1 4 1 3 4 2 3 1 8 5 2 5 2 3 10 1 2 1 100 1 2 10000 1 2 100000 1
YES NO
/**
hdu4284 状态压缩dp
题目大意：给定一个城市网络，要求从1出发在回到1，必须经过指定的一些点并在这些点中打工，打工可以挣一些路费，但是事先需要买许可证，问能否按照
要求最终回到1点
解题思路：一开始以为是图论题，想偏了== 指定的点最多有15个，我们可以用dp[st][j] 表示在st状态下最终留在j点剩下的最多钱。floy预处理点与点之间
的最短距离，然后状态转移即可。方程为：dp[s][i]=max(dp[s][i],dp[s'][j]-g[j][i]-d[i]+c[i]);
*/
#include <string.h>
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int g[155][155];
int dp[1<<16][16];
int num[22],earn[22],cost[22];
int n,m,mon;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&mon);
memset(g,inf,sizeof(g));
for(int i=1;i<=n;i++)
g[i][i]=0;
int a,b,c;
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
if(c<g[a][b])/// 有重边
g[a][b]=g[b][a]=c;
}
///预处理最短路
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
if(g[i][k]!=inf)
{
for(int j=1;j<=n;j++)
{
if(g[k][j]!=inf)
{
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
}
}
}
}
memset(dp,-1,sizeof(dp));
int h,tmp;
scanf("%d",&h);
for(int i=0;i<h;i++)
{
scanf("%d%d%d",&num[i],&earn[i],&cost[i]);
}
for(int i=0;i<h;i++)
{
tmp=mon-g[1][num[i]]-cost[i];
if(tmp>=0)///先初始化1到每个指定点
{
dp[1<<i][i]=tmp+earn[i];
}
}
int st=(1<<h)-1;
for(int i=1;i<=st;i++)
{
for(int j=0;j<h;j++)
{
if(dp[i][j]<0)continue;
for(int k=0;k<h;k++)
{
if(i&(1<<k))continue;
tmp=dp[i][j]-g[num[j]][num[k]]-cost[k];
if(tmp>=0)
{
tmp+=earn[k];
int stat=i|(1<<k);
dp[stat][k]=max(dp[stat][k],tmp);
}
}
}
}
int flag=0;
for(int i=0;i<h;i++)
{
tmp=dp[st][i]-g[num[i]][1];//最后还要回到1点
if(tmp>=0)
{
flag=1;
break;
}
}
if(flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
原文：http://blog.csdn.net/lvshubao1314/article/details/44656349