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<