ural 1500 Pass Licenses --- 状态压缩dfs - c++编程基础

这方法真好啊。。

有n个点，m条路，k个执照，每条路都属于一些执照（拥有指定执照才能走）

求从0走到1 最少需要哪些执照

枚举 1到1<

对每一种组合dfs 取二进制中1最少的解咯

代码很简洁但熟练运用二进制总是需要多多练习的事。。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #define inf 0x3f3f3f3f using namespace std; //mp[i][j]中为1的位表示，拥有该位的执照就可以走i到j这条路 int mp[35][35],vis[35],k,n,m,tmp,ans1[35],ans,tmp1[35]; void dfs(int x,int now) { vis[x]=1; if(x==1) return; for(int i=0;i
           
            >=1; } if(cnt>=ans) continue; now=i; memset(vis,0,sizeof vis); dfs(0,now); // printf("vis1:%d i:%d\n",vis[1],i); if(vis[1])//能够走到1 则比较执照数量 { ans=0;cnt=0; while(now) { // printf("tmp:%d cnt:%d\n",tmp,cnt); if(now&1) { ans1[ans]=cnt; ans++; } now>>=1; cnt++; } } } printf("%d\n",ans); for(i=0;i