Ural 1500Pass Licenses(状态压缩dfs)

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

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

枚举 0到k-1 二进制的每一位代表是否拥有该执照，那么只用枚举状态0~(2^(k-1)-1)即可。表示执照是否存在的状态，然后就是dfs暴搜了，在搜的过程中，如果这个状态的需要执照个数>=可行解的最小值，那么不需要搜索，直接换另一种状态。详见代码：

#include
  
   
#include
   
     #include
    
      using namespace std; int mp[35][35]; int visi[35]; int rans[35]; int n; void dfs(int p,int c) { visi[p]=1; if(p==1) return; for(int i=0;i
     
      >k>>n>>m) //n个结点,m条路,k种护照 { memset(mp,0,sizeof(mp)); while(m--) { scanf("%d%d%d",&a,&b,&c); mp[a][b]=(mp[a][b]|(1<
      
       =2^20即可 int tmp,cnt,q; int res; //tmp记录状态 cnt记录最小的满足条件个数 for(i=0;i<(1<
       
        =ans的不要 { if(tmp&1) cnt++; tmp>>=1; } if(cnt>=ans) continue; tmp=q; memset(visi,0,sizeof(visi)); dfs(0,tmp); if(visi[1]) { ans=0; res=tmp; while(tmp) { if(tmp&1) ans++; tmp>>=1; } } } int t=0; q=0; while(res) { if(res&1) rans[t++]=q; res>>=1; q++; } cout<