首页 程序设计 图与树 最短路算法

# 或 - 最短路 - ABC-408-E

# 题目大意

现有一个 nn 个点 mm 条边的无向连通图，请你求出，顶点 1→1 \to 顶点 nn 的路径中，所有边的权值或 OROR 最小值

  • 可能存在重边

# 数据范围

  • 2≤N≤2×1052 \le N \le 2 \times 10^5
  • N−1≤M≤2×105N - 1 \le M \le 2 \times 10^5
  • 0 \le w_i \le 2^

# 题解

此处不另附 DSUDSU 并查集板子

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve () {
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= m; i++)
        cin >> u >> v >> w, g.push_back({u, v, w});

        int res = (1 << 30) - 1;

        for (int i = 29; i >= 0; i--) {
            res -= (1 << i), dsu.init(n);

            for (auto [u, v, w] : g)
                if ((res | w) == res)
                    dsu.merge(u, v);
            
            if (dsu.find(1) != dsu.find(n))
                res += (1 << i);
        }

        cout << res << '\n';
}

# 异或 - 最短路 CF845G

# 题目大意

现有一个 nn 个点 mm 条边的无向连通图，请你求出，顶点 1→1 \to 顶点 nn 的路径中，所有边的权值异或 XORXOR 最小值

# 数据范围

  • 1≤n≤1061 \le n \le 10^6
  • 0≤w≤1080 \le w \le 10^8

# 题解

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
typedef pair<int, int> PII;
const int N = 1e5 + 10;

struct LinearBasis {
    vector<int> a = vector<int>(65);

    int insert(int x) {
        for (int i = 62; i >= 0; i--)
            if ((x >> i) & 1) {
                if (!a[i]) {
                    a[i] = x;
                    return 1;
                }
                else
                    x ^= a[i];
            }
        return 0;
    }

    int qMin(int ret = 0) {
        for (int i = 62; i >= 0; i--)
            ret = min(ret, ret ^ a[i]);
        return ret;
    }
} lb;

int n, m;
vector<bool> st;
vector<int> dis;
vector<PII> g[N];

void dfs(int u, int f) {
    st[u] = 1;
    for (auto [to, val] : g[u]) {
        if (to != f) {
            if (!st[to])
                dis[to] = dis[u] ^ val, dfs(to, u);
            else
                lb.insert(dis[u] ^ dis[to] ^ val);
        }
    }
}

void solve () {
    cin >> n >> m, st = vector<bool>(n + 1), dis = vector<int>(n + 1);
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w}), g[v].push_back({u, w});
    }

    dfs(1, 0);

    cout << lb.qMin(dis[1] ^ dis[n]) << '\n';
}