题解：AT_abc396_d [ABC396D] Minimum XOR Path

· · 题解

思路：

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

首先，我们用 dfs 求出求出所有 1 到 N 的所有简单路径，同时记录一下异或值，到达 N 号点就将其与原答案取一个最小值就行了。

注意 ans 初始时要设为 2 \times 10^{18}，设为 10^{18} 时会 WA 两个点。

代码：

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