题解：AT_abc396_d [ABC396D] Minimum XOR Path

MutU · 2025-03-09 09:18:49 · 题解

暴搜就好了，这里直接用邻接矩阵存图跑得飞快。

答案初始值一定要开大！1\times10^{18} 会 WA 导致我吃了一发罚时

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 21;
int n,ans=pow(2,61),m;
int p[N][N];
int vis[N];
inline void dfs(int u,int val){
    if(u==n){
        ans=min(ans,val);
        return;
    }
    vis[u]=true;
    for(int i=1;i<=n;i++){
        if(p[u][i]!=-1 && !vis[i]){
            dfs(i,val xor p[u][i]);
        }
    }
    vis[u]=false;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    memset(p,-1,sizeof(p));
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        p[u][v]=p[v][u]=w;
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}