题解：AT_abc396_d [ABC396D] Minimum XOR Path

· · 题解

题目传送门

题目简述

一个简单无向图有 n 个顶点和 m 条边。边 i 连接顶点 u_{i} 和 v_{i}，权值为 w_{i}。求顶点 1 到 顶点 N 的所有简单路径中，路径上的边的最小异或和。

主要思路

一道比较板的 dfs 题，由于 N \le 10，所以也不需要进行优化。边可以用邻接表记录，从顶点 1 开始依次遍历每条路径即可。注意：标记走过的顶点时，顶点 1 在 dfs 前要标记。

由于 w_{i} < 2^{60}，所以十年 OI 一场空，_____。

AC Code

#include<set>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
typedef long double db;
const int INT_INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
// ----------------------------

// ----------------------------
int n;
bool vis[20];
ll ans = LL_INF;
set<pair<int, ll> > st[11];
// ----------------------------
void dfs(int u, ll sum) {
    if (u == n) {
        ans = min(ans, sum);
        return;
    }
    for (auto i : st[u]) {
        if (!vis[i.first]) {
            vis[i.first] = true;
            dfs(i.first, sum ^ i.second);
            vis[i.first] = false;
        }
    }
}

int main() {
    int m, u, v; ll w; cin >> n >> m;
    for (int _ = 1; _ <= m; _++) {
        cin >> u >> v >> w;
        st[u].insert(make_pair(v, w));
        st[v].insert(make_pair(u, w));
    }
    // ----------------------------
    vis[1] = true;
    dfs(1, 0);
    // ----------------------------
    cout << ans;
    return 0;
}