解题思路

给定一条从 1 到 $u$ 的简单路径，允许至多一次选择一个连续边段 $[l,r]$ 把该段内每条边权 $w$ 改为 $w\oplus x$ 后再求路径边权和的最小值。等价地看：沿着路径行进时，我们会有三种“状态”：

• 状态 0：尚未开始异或段（之后的某一段可开始，也可以永不开始）；
• 状态 1：正处于异或段中（本段内边权以 $w\oplus x$ 计）；
• 状态 2：已结束异或段（之后再以原权 $w$ 行走，不可再开启）。

把“路径上一段用 $w\oplus x$”的限制，转化为分层图最短路（Dijkstra）：

• 把原图每个点 $v$ 复制三层 $(v,0),(v,1),(v,2)$ 分别代表上述三状态；

• 对每条原边 $(u\to v, w)$ 添加如下 6 条转移（均为非负权，适用 Dijkstra）：

  • $(u,0)\to (v,0)$：成本 $w$（仍未开始）
  • $(u,0)\to (v,1)$：成本 $w\oplus x$（在此边“开启”异或段）
  • $(u,0)\to (v,2)$：成本 $w\oplus x$（异或段长度为 1，开启并在此边“结束”）
  • $(u,1)\to (v,1)$：成本 $w\oplus x$（继续处于段内）
  • $(u,1)\to (v,2)$：成本 $w\oplus x$（以此边作为段内最后一条边，随后进入已结束）
  • $(u,2)\to (v,2)$：成本 $w$（已经结束，仅按原权前进）

为何需要 $(u,0)\to (v,2)$？为了允许“中间某一条边单独作为异或段”（长度为 1 且不在末尾）。若没有这条边，只能在下一条边结束，导致段长 $\ge 2$。

起点为 $(1,0)$（尚未开始，代价 0）。对每个结点 $i$，允许在任意状态结束（段可以没开、在最后一条边结束、或已经结束），因此答案为

若均不可达则输出 $-1$。

算法要点：分层建图（3 倍结点、约 6 倍边），全程边权非负，直接 Dijkstra。

复杂度分析

• 结点数：$3n$；边数：约 $6m$。
• Dijkstra 时间复杂度：$O\big((n+m)\log n\big)$（精确为 $O((3n+6m)\log(3n))$）。
• 空间复杂度：$O(n+m)$（存 3 层距离与 6 倍边）。

代码实现

Python

# 分层图 + Dijkstra；允许在任意状态结束
import sys
import heapq

INF = 10**30

def dijkstra(n, edges, x):
    # 构建 3 层图：节点编号为 0..3*n-1，层偏移为 off=layer*n
    N = n * 3
    g = [[] for _ in range(N)]
    for u, v, w in edges:
        u -= 1; v -= 1
        wx = w ^ x
        # (u,0)->(v,0/1/2)
        g[u + 0*n].append((v + 0*n, w))
        g[u + 0*n].append((v + 1*n, wx))
        g[u + 0*n].append((v + 2*n, wx))  # 段长=1
        # (u,1)->(v,1/2)
        g[u + 1*n].append((v + 1*n, wx))
        g[u + 1*n].append((v + 2*n, wx))  # 在此边结束
        # (u,2)->(v,2)
        g[u + 2*n].append((v + 2*n, w))

    dist = [INF] * N
    start = 0  # (1,0)
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:
            continue
        for v, w in g[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    # 取每个原节点三层的最小值
    ans = []
    for i in range(n):
        best = min(dist[i + 0*n], dist[i + 1*n], dist[i + 2*n])
        ans.append(-1 if best >= INF//2 else best)
    return ans

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    n = next(it); m = next(it); x = next(it)
    edges = []
    for _ in range(m):
        u = next(it); v = next(it); w = next(it)
        edges.append((u, v, w))
    res = dijkstra(n, edges, x)
    print(" ".join(map(str, res)))

if __name__ == "__main__":
    main()

Java

// 分层图 + Dijkstra；不使用快读，采用 Scanner 读入
import java.util.*;

public class Main {
    static final long INF = (long)4e18;

    // 加边（数组邻接表）
    static void addEdge(int[] head, int[] to, long[] w, int[] next, int[] idxRef, int u, int v, long ww) {
        int idx = idxRef[0];
        to[idx] = v;
        w[idx] = ww;
        next[idx] = head[u];
        head[u] = idx;
        idxRef[0] = idx + 1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        long x = sc.nextLong();

        int N = n * 3;        // 三层节点
        int M = m * 6;        // 每条原边扩展 6 条
        int[] head = new int[N];
        Arrays.fill(head, -1);
        int[] to = new int[M];
        long[] w = new long[M];
        int[] next = new int[M];
        int[] idxRef = new int[]{0}; // 辅助记录当前边下标

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            long ww = sc.nextLong();
            u--; v--;
            long wx = ww ^ x;

            // (u,0)->(v,0/1/2)
            addEdge(head, to, w, next, idxRef, u + 0*n, v + 0*n, ww);
            addEdge(head, to, w, next, idxRef, u + 0*n, v + 1*n, wx);
            addEdge(head, to, w, next, idxRef, u + 0*n, v + 2*n, wx);  // 段长=1

            // (u,1)->(v,1/2)
            addEdge(head, to, w, next, idxRef, u + 1*n, v + 1*n, wx);
            addEdge(head, to, w, next, idxRef, u + 1*n, v + 2*n, wx);  // 在此边结束

            // (u,2)->(v,2)
            addEdge(head, to, w, next, idxRef, u + 2*n, v + 2*n, ww);
        }

        // Dijkstra
        long[] dist = new long[N];
        Arrays.fill(dist, INF);
        boolean[] vis = new boolean[N];
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));

        int start = 0; // (1,0)
        dist[start] = 0;
        pq.add(new long[]{0L, start});

        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long d = cur[0];
            int u = (int)cur[1];
            if (vis[u]) continue;
            vis[u] = true;

            for (int e = head[u]; e != -1; e = next[e]) {
                int v = to[e];
                long nd = d + w[e];
                if (nd < dist[v]) {
                    dist[v] = nd;
                    pq.add(new long[]{nd, v});
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            long best = Math.min(dist[i + 0*n], Math.min(dist[i + 1*n], dist[i + 2*n]));
            if (best >= INF / 2) sb.append(-1);
            else sb.append(best);
            if (i + 1 < n) sb.append(' ');
        }
        System.out.println(sb.toString());
        sc.close();
    }
}

C++

// 分层图 + Dijkstra（数组链式前向星）
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = (ll)4e18;

struct Edge {
    int to, next;
    ll w;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    long long x;
    if (!(cin >> n >> m >> x)) return 0;

    int N = n * 3;
    int M = m * 6;                 // 每条原边扩展 6 条
    vector<int> head(N, -1);
    vector<Edge> es; es.reserve(M);
    auto add = [&](int u, int v, ll w) {
        es.push_back({v, head[u], w});
        head[u] = (int)es.size() - 1;
    };

    for (int i = 0; i < m; ++i) {
        int u, v; ll w;
        cin >> u >> v >> w;
        --u; --v;
        ll wx = w ^ x;
        // (u,0)->(v,0/1/2)
        add(u + 0*n, v + 0*n, w);
        add(u + 0*n, v + 1*n, wx);
        add(u + 0*n, v + 2*n, wx);       // 段长=1
        // (u,1)->(v,1/2)
        add(u + 1*n, v + 1*n, wx);
        add(u + 1*n, v + 2*n, wx);       // 在此边结束
        // (u,2)->(v,2)
        add(u + 2*n, v + 2*n, w);
    }

    // Dijkstra
    vector<ll> dist(N, INF);
    vector<char> vis(N, 0);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    int s = 0; // (1,0)
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i != -1; i = es[i].next) {
            int v = es[i].to;
            ll nd = d + es[i].w;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.push({nd, v});
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        ll best = min(dist[i + 0*n], min(dist[i + 1*n], dist[i + 2*n]));
        if (best >= INF / 2) cout << -1;
        else cout << best;
        if (i + 1 < n) cout << ' ';
    }
    cout << '\n';
    return 0;
}

题目内容

给定一个有 $n$ 个结点以及 $m$ 条的带权有向图 $G$ ，以及一个整数 $x$ 。$G$ 中保证没有自环。

米小游初始在结点 $1$。对于一条从 $1$ 到 $u$ 的长度$k$ 为的 简单路径，设其经过的 点 为$p_1,p_2,...,p_{k+1}$，其中 $p_1=1,p_{k+1}=u$ ，且对于所有 $1≤i≤k$，$G$ 中都存在一条 $p_i$ 从到 $p_{i+1}$ 的有向边。这条路径的代价计算方式如下：

• 米小游可以选择两个整数 $l,r$ ，满足 $1≤l≤r≤k$ 。接下来，对于所有的 $l≤i≤r$，米小游将到这条有向边的边权异或上 $x$ 。也就是说，如果原本这条边的边权为 $w$ ，米小游会将其修改为 $w⊕x$ ，其中 $⊕$ 代表按位异或。本操作最多执行一次。
• 路径的代价即为修改之后，所有其经过的边的边权和。
• 从结点 $1$ 到 $i$ 的最小代价即为所有可能的从结点 $1$ 到 $i$ 的路径中的最小代价。

米小游想知道，在这样的代价计算方式下，他到过每个结点的最小代价分别是多少。

注意：为某条路径选定并执行异或操作后，仅用于计算该路径的代价；图本身不会被真正修改，评估其他路径时可重新自由选择 $l,r$ ，或不执行此操作。

【名词解释】

简单路径：不经过重复点和重复边的路径。

输入描述

第一行输入三个整数 $n,m,x(2≤n≤10^5,1≤m≤2·10^5,0≤x≤10^9)$ ，分别表示 $G$ 中的结点数量、边数，以及异或时常数。 接下来 $m$ 行，每行输入三个整数 $u_i,v_i,w_i(1≤u_i,v_i≤n,0≤w_i≤10^9)$ ，代表一条从结点 $u_i$ 到 $v_i$，边权为 $w_i$ 的有向边。输入保证 $G$ 中不存在自环。

输出描述

输出一行 $n$ 个整数，其中第 $i$ 个整数代表从结点 $1$ 到 $i$ 的路径的最小代价，无法到达则第 $i$ 个整数为 $-1$ 。

样例1

输入

5 5 2
1 2 2
1 5 3
5 3 4
2 4 10
1 4 9

输出

0 0 5 8 1

说明

对于结点 $4$ ，米小游可以选择路径 $1→2→4$ ，并将 $1→2$ 和 $2→4$ 两条有向边的边权异或上，代价为 $(2⊕2)+(10⊕2)=0+8=8$ 。可以证明不存在代价小于 $8$ 的路径。 对于结点 $3$，米小游可以选择路径 $1→5→3$，并将 $1→5$ 这条有向边的边权异或上 $x$ ，代价为 $(3⊕2)+4=1+4=5$。可以证明不存在代价小于 $5$ 的路径。