[数据结构与算法]Atcoder Beginner Contest 244 F

F - Shortest Good Path

题意：

给你n个点，m条边，无重边，无自环

一个数列如果满足，所有的都在1-N并且两点之间有边连就可以

还有1 0表示路径经过i点的次数是奇数还是偶数

题解：

1.如何表示？

（1）输入时用一个vector表示，后续用auto得到对应的值。

（2）dis[i][j]表示现在状态是i「用二进制来表示」，数为j。

2.如何做？

（1）为什么一开始要u-1，v-1？因为要使用二进制的操作，比如0001，是(1<<0)而不是(1<<1)

（2）BFS，从一个数开始往后搜索，如果没搜过，就继续搜，然后+1，如果搜过了，那就不要了

//
#include <iostream>
#include <vector>
#include <queue>
#define int long long
using namespace std;
const int N = (1 << 17);
const int INF = 0x3f3f3f3f3f3f3f3f;
int dis[N][17];
vector<int> G[20];
queue<pair<int, int>> Q;
int n,m;
signed main() {
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		u--,v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	int M = 1<<n;
	for(int i=0;i<M;i++)
		for(int j=0;j<n;j++)
			dis[i][j]=INF;
//		这里为啥要一开始初始化为1呢？
//		因为我一个数，length为1！
	for(int i=0;i<n;i++){
		dis[1<<i][i]=1;
		Q.push({1<<i,i});
	}
	//		BFS
	while(Q.size()){
		int s = Q.front().first;
		int v = Q.front().second;
		Q.pop();
		for(auto u : G[v]){
			int ns = s ^ (1<<u);
			if(dis[ns][u]<INF) continue;
			dis[ns][u] = dis[s][v] + 1;
//			这就是挑出来的那一个
			Q.push({ns,u});
		}
	}
	int ans = 0;
//	最后是对所有情况进行加总
	for(int i=1;i<M;i++){
		int mm = INF;
		for(int j=0;j<n;j++){
			mm = min(mm,dis[i][j]);
		}
		ans += mm;
	}
	cout<<ans<<endl;
}