hdu 4284 TSP问题

#include <cstdio>  
#include <iostream>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
int n,m;  
int money;  
int maps[105][105];  
int dp[17][1<<17];  
void debug(int x,int y)  
{  
    printf("dp[%d][%d]=%d\n",x,y,dp[x][y]);  
}  
int main()  
{  
    int cas;  
    int a,b,cc,d;  
    scanf("%d",&cas);  
    while(cas--)  
    {  
        scanf("%d%d%d",&n,&m,&money);  
        memset(maps,0x3f,sizeof(maps));  
        for(int i=1;i<=m;i++)  
        {  
           scanf("%d%d%d",&a,&b,&cc);  
           if(cc<maps[a][b])maps[a][b]=maps[b][a]=cc;  
        }  
        for(int i=1;i<=n;i++) maps[i][i]=0;  
        for(int k=1;k<=n;k++)  
        {  
            for(int i=1;i<=n;i++)  
            {  
                for(int j=1;j<=n;j++)  
                {  
                    maps[i][j]=min(maps[i][k]+maps[k][j],maps[i][j]);  
                }  
            }  
        }  
        int h;  
        int id[16];  
        int g[16];  
        int c[16];  
        scanf("%d",&h);  
        for(int i=1;i<=h;i++)  
        {  
            scanf("%d%d%d",&a,&b,&d);  
            id[i]=a;  
            c[i]=d;  
            g[i]=b;  
        }  
        memset(dp,-0x3f,sizeof(dp));  
        int sums=(1<<h);  
        for(int i=1;i<=h;i++)  
        {  
            if(money-maps[1][id[i]]-c[i]>=0) dp[i][1<<(i-1)]=money-maps[1][id[i]]-c[i]+g[i];  
        }  
        for(int i=1;i<sums;i++)  
        {  
            for(int j=0;j<h;j++)  
            {  
                if((i>>j)&1)  
                {  
                    for(int k=0;k<h;k++)  
                    {  
                        if( ((i>>k)&1) && dp[k+1][i&(~(1<<j))]-maps[id[k+1]][id[j+1]]-c[j+1]>=0)  
                        {  
                            dp[j+1][i]=max(dp[j+1][i],dp[k+1][i&(~(1<<j))]-maps[id[k+1]][id[j+1]]-c[j+1]+g[j+1]);  
                        }  
                    }  
                }  
            }  
        }  
        int ok=0;  
        for(int i=1;i<=h;i++)  
        {  
            if(dp[i][sums-1]-maps[id[i]][1]>=0) ok=1;  
        }  
        printf("%s\n",ok?"YES":"NO");  
    }  
    return 0;  
}