题解：AT_abc396_d [ABC396D] Minimum XOR Path

思路：

这一题不是很难，我们只要按着题意模拟就行了。

首先，我们用 dfs 求出求出所有

1

到

N

的所有简单路径，同时记录一下异或值，到达

N

号点就将其与原答案取一个最小值就行了。

注意

ans

初始时要设为

2 \times 10^{18}

，设为

10^{18}

时会 WA 两个点。

代码：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans=2e18;
bool f[15];
vector<pair<int,int> >e[15];
void dfs(int x,int sum){
	if(x==n){
		ans=min(ans,sum);
		return;
	}
	for(auto[a,b]:e[x]){
		if(f[a]) continue;
		f[a]=1;
		dfs(a,sum^b);
		f[a]=0;
	}
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int u,v,w;cin>>u>>v>>w;
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
	f[1]=1;
	dfs(1,0);
	cout<<ans;
	return 0;
}

题解：AT_abc396_d [ABC396D] Minimum XOR Path

文章操作

思路：

代码：

相关推荐

评论

题解：AT_abc396_d [ABC396D] Minimum XOR Path