题目传送门：F - Shortest Good Path (atcoder.jp)

啊shit，这题没做出来啊。这个dp状态属实想不到，之前写了好几次dfs都T了，看了题解才明白，用bfs好多了。

dfs无法保证第一个拓展到的点是长度最短的，但是bfs可以，然后下一次就不会拓展已经拓展了的点。于是bfs的复杂度比dfs低了很多。

题目大意

有一个N个点，M条无向边，现在有2^N条线路，分别是0 ~ N - 1的二进制表示，比如0010表示编号为12 4的点走了偶数次，编号为3的点走了奇数次，数据保证一定存在这么多条路径。

求满足数字(0~2^N - 1)条件的路径的最小长度的和，举个例子，要满足101的路径可能是1->2->3->2，长度为4，要满足000的路径长度就是0。

思路

还是一个dp题，和E题《[AtCoder Beginner Contest 244]E – King Bombee（DP动态规划） – ErikTse Runtime》有异曲同工之妙。

但是F题的dp并不是循环可以做的dp，其实是一个bfs做的dp。

dp[i][j]的含义：dp[终点][路径]，这里的路径S（S是一个0~2^N - 1的数字）用一个十进制数表示，因为N最大是17，所以开十几万大小就够了。

dp数组初始化为inf，或者-1也行，表示没走到过。

那么容易得到状态转移方程：

因为从U走到V，这里的路径变化就是V所在的二进制位异或了一个1，就如上述公式一样的变化。

我们的二进制位的第0位表示路径的1号点，也就是i位表示i+1号点，所以需要V - 1。

最后在统计答案的时候，需要对每个要求路径(1~2^N - 1)求一下终点为1~N的所有可能的最小长度，再将所有要求路径求和即可。

代码中注释比较详细。

代码

#include <bits/stdc++.h>
#define sc scanf
#define pr printf
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;

typedef pair<int, int> PII;
const int maxn = 2e5 + 10,inf = 1e8;
int N, M;
vector<int> g[maxn];//存图 
int dp[18][maxn];//dp[终点][路径]

void bfs(int u,int s)
{
	queue<PII> q;
	q.push({u, s});//终点，路径 
	dp[u][s] = 0;//初始化dp 
	while(!q.empty())
	{
		int U = q.front().fi, S = q.front().se;q.pop();//提取信息，记得pop 
		for(auto V : g[U])
		{
			int nS = S ^ (1 << (V - 1));//算出下一个点的路径 
			if(dp[V][nS] != -1)continue;//BFS保证第一次更新到的点一定是长度最小的，所以如果更新过就不要再更新了 
			dp[V][nS] = dp[U][S] + 1;//状态转移 
			q.push({V, nS});
		}
	}
	return;
}  

signed main()
{
	cin >> N >> M;
	for(int i = 1;i <= M; ++ i)
	{
		int x, y;cin >> x >> y;
		g[x].pb(y);g[y].pb(x);//双向存图 
	}
	for(int i = 1;i <= N; ++ i)g[0].pb(i);//存从0开始到所有正整数的边，方便从0开始bfs 
	for(int i = 0;i < (1 << N); ++ i) for(int j = 0;j <= 17; ++ j)dp[j][i] = -1;//初始化dp数组 
	bfs(0, 0);
	int ans = 0;
	for(int i = 1;i < (1 << N); ++ i)//i为路径 
	{
		int tmp = inf;
		for(int j = 1;j <= N; ++ j)	tmp = min(tmp, dp[j][i]);
		ans += tmp;
	}
	pr("%lld\n",ans);
	return 0;
}