裸的TSP
#include#include #include #include 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 =0) dp[i][1<<(i-1)]=money-maps[1][id[i]]-c[i]+g[i]; } for(int i=1;i>j)&1) { for(int k=0;k >k)&1) && dp[k+1][i&(~(1< =0) { dp[j+1][i]=max(dp[j+1][i],dp[k+1][i&(~(1< =0) ok=1; } printf("%s\n",ok "YES":"NO"); } return 0; }