题解：AT_abc396_d [ABC396D] Minimum XOR Path

ZZ0520 · 2025-03-09 14:35:09 · 题解

题面

题目描述

给定一个简单的连通无向图，其中 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

#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;
}