AT_abc396_d.[ABC396D] Minimum XOR Path

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个简单连通无向图，包含 $N$ 个顶点（编号为 $1$ 至 $N$ ）和 $M$ 条边（编号为 $1$ 至 $M$ ）。边 $i$ 连接顶点 $u_i$ 和 $v_i$ ，并带有标签 $w_i$ 。

请找出从顶点 $1$ 到顶点 $N$ 的所有简单路径（不重复经过顶点的路径）中，路径上所有边标签的总异或值的最小可能值。

关于异或（XOR）的定义：
对于非负整数 $A$ 和 $B$ ，它们的异或 $A \oplus B$ 定义如下：

$A \oplus B$ 的二进制表示中， $2^k$ 位（ $k \geq 0$ ）的值为 $1$ ，当且仅当 $A$ 和 $B$ 在 $2^k$ 位上的值不同；否则为 $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)$ ，且其值与运算顺序无关。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$
$u_1$ $v_1$ $w_1$
$u_2$ $v_2$ $w_2$
$\vdots$
$u_M$ $v_M$ $w_M$

输出格式

输出答案。

输入输出样例

输入#1
```
4 4
1 2 3
2 4 5
1 3 4
3 4 7
```
输出#1
```
3
```
输入#2
```
4 3
1 2 1
2 3 2
3 4 4
```
输出#2
```
7
```

输入#3

7 10
1 2 726259430069220777
1 4 988687862609183408
1 5 298079271598409137
1 6 920499328385871537
1 7 763940148194103497
2 4 382710956291350101
3 4 770341659133285654
3 5 422036395078103425
3 6 472678770470637382
5 7 938201660808593198

输出#3

186751192333709144

说明/提示

约束条件

$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}$
输入的图是简单连通无向图
输入中的所有值均为整数

样例解释 1

从顶点 $1$ 到顶点 $4$ 存在以下两条简单路径：

顶点 $1$ → 顶点 $2$ → 顶点 $4$
路径上的边标签总异或值为 $6$ 。
顶点 $1$ → 顶点 $3$ → 顶点 $4$
路径上的边标签总异或值为 $3$ 。
因此，最小值为 $3$ 。

翻译由 DeepSeek R1 完成

输入解题思路，AI测评打分。不知道怎么写?

首页