hdu 4284 floyd+暴搜

注意到H (H <= 15) 所以 可以 选择 状压+dp

但是 直接用搜索也可以过。经典的TSP问题。

#include
  
   
#include
   
     #include
    
      using namespace std; int Map[150][150]; const int INF=1<<29; struct node { int v; int get,pay; }s[20]; int n,m,money; int vis[150]; int h; void floyd() { int i,j,k; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++){ if(i==j||i==k||j==k) continue; Map[i][j]=min(Map[i][j],Map[i][k]+Map[k][j]); } } int dfs(int u,int leave,int number) { int i; if(number==h){ if(leave>=Map[u][1]) return 1; return 0; } for(i=0;i
     
      =Map[u][s[i].v]+s[i].pay){ vis[s[i].v]=1; if(dfs(s[i].v,leave-Map[u][s[i].v]-s[i].pay+s[i].get,number+1)) return 1; vis[s[i].v]=0; } } } return 0; } int main() { int t,i,j; scanf("%d",&t); while(t--){ memset(vis,0,sizeof(vis)); scanf("%d%d%d",&n,&m,&money); //memset(Map,0,sizeof(Map)); for(i=1;i<=n;i++){ for(j=1;j<=n;j++) Map[i][j]=INF; Map[i][i]=0; } for(i=0;i