题解：AT_abc396_d [ABC396D] Minimum XOR Path

题面

题目描述

给定一个简单的连通无向图，其中

N

顶点编号为

1

到

N

，

M

边编号为

1

到

M

。边

i

连接顶点

u_i

和

v_i

，并有一个标签

w_i

。

在从顶点

1

到顶点

N

的所有简单路径（不多次经过同一顶点的路径）中，求出该路径上边的标号的最小异或。

对于非负整数

A

和

B

，它们的异或

A \oplus B

定义如下：

在 $A \oplus B$ 的二进制表示中， $2^k \,(k \ge 0)$ 对应位置上的数字是 $1$ ，当且仅当 $A$ 和 $B$ 的同一位置上的数字之一恰好是 $1$ ；否则为 $0$ 。

例如，

3 \oplus 5 = 6

（二进制：

011 \oplus 101 = 110

）。

一般来说，

k

整数

p_1, \dots, p_k

的异或定义为

(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)

。可以证明它不依赖于

p_1, \dots, p_k

的阶数。

数据范围

$2 \leq N \leq 10$
$N-1 \leq M \leq \frac{N(N-1)}{2}$
$1 \leq u_i < v_i \leq N$
$0 \leq w_i < 2^{60}$
给定图是一个简单连通无向图。
所有输入值均为整数。

思路

首先我们注意到

N \leq 10

，所以我们可以直接通过 DFS 跑所有的情况。

注意：数据范围比较大所以需要开 long long。

Code

CPP

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
#define int long long
vector<pair<int,int>> g[N];
int n,m,vis[N],ans=9e18;
void dfs(int u,int c){
	if(u==n){
		ans=min(ans,c);
	}
	for(auto [v,w]:g[u]){
		if(vis[v]){
			continue;
		}
		vis[v]=1;
		dfs(v,c^w);
		vis[v]=0;
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});//记录路径 
		g[v].push_back({u,w});
	}
	vis[1]=1;
	dfs(1,0);
	cout<<ans;
	return 0;
}

题解：AT_abc396_d [ABC396D] Minimum XOR Path

文章操作

题面

题目描述

数据范围

思路

Code

相关推荐

评论

题解：AT_abc396_d [ABC396D] Minimum XOR Path