题目地址：http://acm.fzu.edu.cn/problem.php?pid=2093

首先明确，

///dp题，状态的选取是最重要的。///
状态取的不好，直接导致子问题解决的困难，甚至子问题不能求解。
因为dp要求全局最优，状态取好了，每个阶段子问题的求取是最优的，这个dp才成立。不然就要寻求最优解。
这里题目要求的是需要至少几秒才能必定找到小兔的位置，首先考虑的是我们选取到达某状态所需最少时间设置为子问题的参考量。那么子问题在这个条件下能不能被求解（分解）呢？
很明显，可以。
这里的状态因为信息太多，我们需要压缩。
dp[i]定义为到达状态i，我们需要花费的最少时间。
每个点确定与否也是包含在状态里边的，因为确定与否其实就是01分布，实际上就可以把i j二进制化之后来表示。
用1在对于当前的每个i中表示这个点确定。

f[dx-1]|= 1<<dy-1;
f[dy-1]|= 1<<dx-1;

建边

while(!q.empty())
        {
            int now = q.front();
            q.pop();
            int nxt = 0;
            for (int i=0; i<n; i++) if ((now&f[i])==f[i]) nxt|=1<<i;
            for (int i=0; i<n; i++)
            {
                for (int j=i+1; j<n; j++)
                {
                    if (dp[nxt|(1 << i) | (1 << j)] > dp[now]+1)
                    {
                        dp[nxt|(1 << i) | (1 << j)] = dp[now]+1;
                        q.push(nxt|(1<<i)|(1<<j));
                    }
                }
            }
        }
        for (int i=0; i<n; i++) dp[(1<<n)-1]=min(dp[(1<<n)-1], dp[((1<<n)-1)^(1 << i)]);

对于每个点，每个点的下一层确定的时候，这个点就一定确定了。
不然选择两个点来确定，接着，所有点都明确了，或者只有一个点没有明确时，我们就知道兔子的位置了。

这里确定下一层的话，用queue模型当然是最吼滴。操作也方便。
那么总的dp方程为：

dp[(1 <<n)-1]=min(dp[(1<<n)-1], dp[((1<<n)-1)^(1 << i)]);

AC代码：

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn = 1<<16;
const long long inf = 0x3f3f3f3f;
int m,n,dp[maxn],f[maxn];
int dx,dy;
queue<int>q;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        memset(f,0,sizeof(f));
        for (int i=1; i<(1<<n); i++) dp[i]=inf;
        while(m--)
        {
            cin>>dx>>dy;
            f[dx-1]|= 1<<dy-1;
            f[dy-1]|= 1<<dx-1;
        }
        for (int i=0; i<n; i++) if(!f[i])f[i]=1<<i;
        while(!q.empty())q.pop();
        q.push(0);
        while(!q.empty())
        {
            int now = q.front();
            q.pop();
            int nxt = 0;
            for (int i=0; i<n; i++) if ((now&f[i])==f[i]) nxt|=1<<i;
            for (int i=0; i<n; i++)
            {
                for (int j=i+1; j<n; j++)
                {
                    if (dp[nxt|(1 << i) | (1 << j)] > dp[now]+1)
                    {
                        dp[nxt|(1 << i) | (1 << j)] = dp[now]+1;
                        q.push(nxt|(1<<i)|(1<<j));
                    }
                }
            }
        }
        for (int i=0; i<n; i++) dp[(1<<n)-1]=min(dp[(1<<n)-1], dp[((1<<n)-1)^(1 << i)]);
        if(dp[(1<<n)-1] == inf)cout<<"-1"<<endl;
        else cout<<dp[(1<<n)-1]<<endl;
    }
}