纯粹广搜,寄了……
查看原帖
纯粹广搜,寄了……
658786
STUDENT00楼主2022/10/1 20:36

是map的问题吗?

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
vector<int> w[35];
struct node{
	long long a;
	int s;
};
queue<node> qt;
map<long long,bool> vis;
long long ed;
void put(long long &a,int b){
	if((a>>b)&1LL) a-=(1<<b);
	else a+=(1<<b);
}
int main(){
	scanf("%d%d",&n,&m);
	ed=(1LL<<n)-1;
	while(m--){
		scanf("%d%d",&a,&b);
		a--;
		b--;
		w[a].push_back(b);
		w[b].push_back(a);
	}
	qt.push({0,0});
	while(!qt.empty()){
		for(int i=0;i<n;i++){
			long long now=qt.front().a;
			put(now,i);
			for(int j=0;j<w[i].size();j++) put(now,w[i][j]);
			if(now==ed){
				printf("%d",qt.front().s+1);
				return 0;
			}
			if(!vis[now]){
				vis[now]=1;
				qt.push({now,qt.front().s+1});
			}
		}
		qt.pop();
	}
	return 0;
}
2022/10/1 20:36
加载中...