#include <bits/stdc++.h>
//#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 5;
int n, m, c, s, t;
int dis[N];
bool vis[N];
vector<PII> g[N];
priority_queue<PII, vector<PII>, greater<PII>> q;
void solve() {
    cin >> n >> m >> c;

    for (int i = 0; i <= n; i ++) {
        for (int j = 1; j <= n; j <<= 1) {
            if ((i ^ j) > n)
                continue;

            g[i].push_back({i ^ j, j * c});
        }
    }

    while (m --) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }

    cin >> s >> t;
    memset(dis, 0x3f, sizeof dis);
    q.push({dis[s] = 0, s});

    while (q.size()) {
        int u = q.top().second;
        q.pop();

        if (vis[u])
            continue;

        vis[u] = 1;

        for (auto [v, w] : g[u]) {
            if (dis[v] > dis[u] + w) {
                q.push({dis[v] = dis[u] + w, v});
            }
        }
    }

    cout << dis[t] << "\n";

}
signed main() {
    //  freopen(".in","r",stdin);
    //  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(12);
    int t = 1;

    //  cin >> t;
    while (t --) {
        solve();
    }

    return 0;
}

企鹅国的最短路径问题 题解

算法标签

单源最短路径、Dijkstra算法（堆优化）、异或性质应用、图论建图优化、优先队列

题目分析

核心问题

给定 $N$ 座城市、$M$ 条单向快捷通道，以及普通路径规则（城市 $i$ 到 $j$ 的时间为 $(i \oplus j) \times C$），求从起点 $A$ 到终点 $B$ 的最短通行时间。

关键痛点

• 普通路径的潜在边数为 $O(N^2)$（任意两座城市间都可通行），若直接建图，当 $N=10^5$ 时会超出时间和空间限制，完全无法处理。
• 需利用异或的数学性质优化边数，同时保证普通路径的权值等价性。
• 所有边权均为正（$C \geq 1$，$j$ 为 2 的幂次故 $j \times C \geq 1$；快捷通道 $V_i \geq 1$），适合用 Dijkstra 算法求解。

异或核心性质（解题关键）

异或是二进制无进位加法，满足三大核心性质：

1. 交换律：$a \oplus b = b \oplus a$；
2. 结合律：$(a \oplus b) \oplus c = a \oplus (b \oplus c)$；
3. 分解性：任意整数的异或结果可拆分为若干个 2 的幂次的异或和（如 $5 = 4 \oplus 1$，对应二进制 $101 = 100 \oplus 001$）。

普通路径权值 $(i \oplus j) \times C$ 可通过拆分异或值转化为多段路径权值之和。例如 $i \oplus j = k_1 \oplus k_2$（$k_1, k_2$ 为 2 的幂次），则 $i \to i \oplus k_1 \to (i \oplus k_1) \oplus k_2 = j$ 的总权值为 $k_1 \times C + k_2 \times C = (k_1 \oplus k_2) \times C = (i \oplus j) \times C$，与直接通行权值完全等价。

核心思路

1. 建图优化：利用异或分解性，不枚举所有普通路径，仅为每个城市 $i$ 连接到 $i \oplus j$（$j$ 为 2 的幂次，且 $i \oplus j \leq N$），边权为 $j \times C$。将边数从 $O(N^2)$ 优化至 $O(N \log N)$（每个城市最多连接 $\log_2 N$ 条边）。
2. 快捷通道整合：直接将 $M$ 条单向快捷通道加入图中，边权为 $V_i$。
3. 堆优化 Dijkstra 算法：用小根堆（优先队列）维护待处理节点，每次弹出当前最短距离的节点，松弛其邻接边，最终得到起点到终点的最短距离。

算法步骤

步骤 1：图的构建

1. 普通路径优化建图：
   • 遍历每个城市 $i$（$0 \leq i \leq N$）；
   • 枚举 $j$ 为 2 的幂次（$j = 1, 2, 4, 8, ...$，直至 $j > N$）；
   • 若 $i \oplus j \leq N$，则添加边 $i \to i \oplus j$，权值为 $j \times C$。
2. 快捷通道建图：遍历 $M$ 条通道，添加单向边 $F_i \to T_i$，权值为 $V_i$。

步骤 2：Dijkstra 算法初始化

• 距离数组 $dis$ 初始化为无穷大（$0x3f3f3f3f$），$dis[s] = 0$（起点距离为 0）；
• 优先队列（小根堆）初始存入 $(0, s)$，表示起点的距离和编号。

步骤 3：堆优化 Dijkstra 执行

1. 弹出堆顶节点 $u$（当前距离最短的未处理节点）；
2. 若节点 $u$ 已标记为处理完成（$vis[u] = 1$），直接跳过；
3. 标记 $u$ 为处理完成，遍历其所有邻接边 $(u \to v, w)$；
4. 若 $dis[v] > dis[u] + w$，更新 $dis[v]$ 并将 $(dis[v], v)$ 加入堆中；
5. 重复上述步骤，直至堆为空。

步骤 4：输出结果

• 最终 $dis[t]$ 即为起点 $s$ 到终点 $t$ 的最短时间。

代码解析

核心数据结构

• 邻接表 $g$：vector<PII> g[N]，存储图的边，每个元素为 $(v, w)$，表示从当前节点到 $v$ 的边权为 $w$。
• 优先队列 $q$：priority_queue<PII, vector<PII>, greater<PII>>，小根堆，按距离从小到大排序，存储 $(dis[u], u)$。
• 距离数组 $dis$：存储起点到各节点的最短距离，初始为无穷大。
• 标记数组 $vis$：标记节点是否已处理完成，避免重复松弛。

关键代码模块

1. 优化建图（普通路径）

for (int i = 0; i <= n; i ++) {
    for (int j = 1; j <= n; j <<= 1) { // j 枚举 2 的幂次
        if ((i ^ j) > n)
            continue; // 确保终点不超出城市编号范围
        g[i].push_back({i ^ j, j * c}); // 添加优化边
    }
}

• 核心逻辑：利用异或分解性，用 $O(N \log N)$ 条边覆盖所有普通路径的连通性和权值等价性。

2. 快捷通道建图

while (m --) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].push_back({v, w}); // 直接添加单向快捷通道
}

3. 堆优化 Dijkstra

memset(dis, 0x3f, sizeof dis);
q.push({dis[s] = 0, s}); // 起点初始化
while (q.size()) {
    int u = q.top().second;
    q.pop();
    if (vis[u]) continue; // 跳过已处理节点
    vis[u] = 1;
    for (auto [v, w] : g[u]) {
        if (dis[v] > dis[u] + w) { // 松弛操作
            q.push({dis[v] = dis[u] + w, v});
        }
    }
}

• 松弛操作：对于每个邻接边，若经节点 $u$ 到 $v$ 的距离更短，则更新并加入堆中。
• 时间优势：堆优化使每次取最短距离节点的时间为 $O(\log V)$，整体时间复杂度为 $O((E + V) \log V)$。

复杂度分析

时间复杂度

• 建图阶段：普通路径优化建图为 $O(N \log N)$（每个节点枚举 $\log_2 N$ 个 2 的幂次），快捷通道建图为 $O(M)$，总建图时间 $O(N \log N + M)$。
• Dijkstra 阶段：堆优化后时间复杂度为 $O((E \log V)$，其中 $E = O(N \log N + M)$（总边数），$V = O(N)$（节点数）。最终整体时间复杂度为 $O((N \log N + M) \log N)$。
• 适配性：对于 $N=10^5$、$M=10^5$，$\log_2 N \approx 17$，总运算量约 $3 \times 10^7$，完全满足时间限制。

空间复杂度

• 邻接表存储边占用 $O(N \log N + M)$ 空间，距离数组、标记数组占用 $O(N)$ 空间，优先队列最大占用 $O(N)$ 空间，整体空间复杂度 $O(N \log N + M)$，可控。

关键注意事项

1. 异或分解的等价性：必须确保拆分后的路径权值与直接普通路径一致，依赖异或的无进位加法性质和 2 的幂次异或无重叠特性。
2. 节点编号范围：建图时需判断 $i \oplus j \leq N$，避免生成超出城市编号的无效边。
3. Dijkstra 的适用性：因所有边权均为正，无需考虑负权边问题，堆优化的 Dijkstra 是最优选择。
4. 输入输出优化：代码中 ios::sync_with_stdio(0); cin.tie(0); 关闭同步，加速输入输出，适配大数据量场景。