P1171 售货员的难题

求最短的哈密顿回路.看见这个 n = 20 n=20 n=20,和哈密顿回路,不难联想到这是一个状态压缩动态规划. 用一个二进制数 s t st st代表是否已经访问过村庄的情况. d p ( i , s t ) : 代表当前在第 i 个点 , 访问情况为 s t dp(i,st):代表当前在第i个点,访问情况为st dp(i,st):代表当前在第i个点,访问情况为st经过的路程 考虑这个状态如何达到的,考虑从某个点 j j j走到了 i i i, 那么这个 j j j点也一定是在 s t st st里边是1的. 如果某个状态 d p ( i , s t ) 不能达到 , 应当设置成 I N F dp(i,st)不能达到,应当设置成INF dp(i,st)不能达到,应当设置成INF,但应当与没有访问过的状态区分开来 可惜,不开O2不能通过下面代码不知道为什么,复杂度 O ( n 2 ∗ 2 n ) O(n^2*2^n) O(n2∗2n)

/*
You held me down but I broke free,
I found the love inside of me.
Now I don't need a hero to survive
Cause I already saved my life.
*/
#include
using namespace std;
const int maxn = (1n;
	for(int i=0;iG[i][j];
	}
	for(int st=0;st