Floyd

GitHub跳转原题关系图返回列表

读懂题面的异或求和程序后,用 Floyd 在 O(n³) 内求出全部点对最短路,不可达保持 10¹⁶,逐对把 Dis(i,j)+f 异或进 S。

OJ: roj

题目 ID: 1421

难度:普及+/提高-

标签:图论最短路Floyd一本通python

创建: 2026-10-07 15:12

更新: 2026-10-07 15:12

形式化题目

给定 nn 个点、mm 条边的有向图,第 ee 条边是 se→tes_e \to t_e,长度为 ded_e(ded_e 可以为负)。 记 aa 到 bb 的最短距离为

Dis(a,b)={a→b 的最短路长度,b 从 a 可达,1016,b 从 a 不可达,Dis(a,a)=0, \mathrm{Dis}(a,b) = \begin{cases} a \to b \text{ 的最短路长度}, & b \text{ 从 } a \text{ 可达},\\ 10^{16}, & b \text{ 从 } a \text{ 不可达}, \end{cases} \qquad \mathrm{Dis}(a,a) = 0 ,

要求输出

S  =  ⨁i=1n⨁j=1n(Dis(i,j)+f),f=1016, S \;=\; \bigoplus_{i=1}^{n} \bigoplus_{j=1}^{n} \bigl(\mathrm{Dis}(i,j) + f\bigr), \qquad f = 10^{16},

其中 ⊕\oplus 表示按位异或,i,ji, j 都按有序点对枚举,(i,j)(i,j) 与 (j,i)(j,i) 各算一次。 数据规模:n⩽500n \leqslant 500,0⩽m⩽2500000 \leqslant m \leqslant 250000,−109⩽de⩽109-10^9 \leqslant d_e \leqslant 10^9, 保证没有负环。

把每一项拆开看:jj 从 ii 不可达时贡献 2×10162 \times 10^{16}(因为 Dis(i,j)\mathrm{Dis}(i,j) 本身就是 ff), 可达时贡献「最短距离 +f+ f」。所以本题只有两件事要做——读懂那段程序, 以及求出所有点对的最短距离。

正解

思路

第一步:那段程序在算什么。 题面给的是一段代码而不是一句话,先把它翻译成人话:

cpp
long long S, f = 1e16;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        S ^= Dis(i, j) + f;

不是求和、不是取模、也不是最大值,而是把 n2n^2 个 Dis(i,j)+f\mathrm{Dis}(i,j)+f 全部异或起来。 异或与顺序无关,于是这个程序的唯一难点就落在了「把 n2n^2 个 Dis(i,j)\mathrm{Dis}(i,j) 都算出来」。

第二步:为什么只能是 Floyd。 需要全源最短路,候选做法有三种,代入 n⩽500n \leqslant 500、m⩽250000m \leqslant 250000 比一比:

做法 复杂度 代入规模 结论
以每个点为源跑堆优化 Dijkstra O(n mlog⁡n)O(n\,m\log n) 500×250000×18≈2.3×109500 \times 250000 \times 18 \approx 2.3 \times 10^9 太慢;而且负权边根本不能直接进 Dijkstra
以每个点为源跑 SPFA 单次最坏 O(nm)O(nm) 最坏 500×500×250000=6.3×1010500 \times 500 \times 250000 = 6.3 \times 10^{10} 卡不住,随时被构造数据打崩
Floyd O(n3)O(n^3) 5003=1.25×108500^3 = 1.25 \times 10^8 可行,而且天然支持负权边(只要无负环)

两个关键点:nn 只有 500500,n3n^3 是 1.25×1081.25 \times 10^8 这个量级,正好是「能过」的规模; 而边权可以为负,这一条直接把 Dijkstra 排除在外(用 Johnson 势函数也要先求一遍最短路,绕回原点)。 所以本题就是 Floyd 的模板题,出题人甚至把「求最短路」这一步藏在了「读懂程序」后面。

第三步:Floyd 的循环不变式。 记 dis[i][j] 为「只允许把编号 ⩽k\leqslant k 的点当作中转点」时 ii 到 jj 的最短距离。外层枚举中转点 kk,内层用 i→k→ji \to k \to j 这条两段路去松弛 i→ji \to j:

dis[i][j]←min⁡(dis[i][j], dis[i][k]+dis[k][j]).\texttt{dis}[i][j] \leftarrow \min\bigl(\texttt{dis}[i][j],\ \texttt{dis}[i][k] + \texttt{dis}[k][j]\bigr).

每跑完一轮 kk,允许的中转点集合就多了一个 kk,不变式成立;当 kk 走到 nn 时中转点不再受限, dis[i][j] 就是真正的最短路。初始化很直接:dis[i][i] = 0(题面规定),其余为 f=1016f = 10^{16}; 读边时 dis[s][t] = min(dis[s][t], d),重边只留最短的一条。

第四步:本题唯一容易踩的坑——负权下 INF 不能直接参与比较。 很多人的 Floyd 模板写成

cpp
// 危险写法:非负权数据上没问题,本题会出错
if (dis[i][k] + dis[k][j] < dis[i][j]) dis[i][j] = dis[i][k] + dis[k][j];

它默认「INF+任何东西>INF\text{INF} + \text{任何东西} > \text{INF}」,这在非负权数据上成立。但本题 ded_e 可以为负: 只要 dis[i][k]<0\texttt{dis}[i][k] < 0 而 dis[k][j]=INF\texttt{dis}[k][j] = \text{INF}(kk 到不了 jj),就有

INF+dis[i][k]  <  INF,\text{INF} + \texttt{dis}[i][k] \;<\; \text{INF},

于是「ii 到 jj 不可达」会被改写成一条超长的假路;更糟的是,这条假路会在后面的轮次里 继续被当作中转使用,错误从一对点扩散到整张表。正确做法是先判可达性再相加:

cpp
if (dis[i][k] == INF) continue; // i 到不了中转点 k,本轮 i 松弛不了任何点
...
if (dis[k][j] == INF) continue; // k 到不了 j,这条 i->k->j 根本不存在

第五步:拿样例走一遍。 样例是 n=2n = 2,三条边:1→21 \to 2 长 11、1→21 \to 2 长 33、2→22 \to 2 长 00。 重边取小后 1→21 \to 2 长 11;点 22 只有一条自环,所以 22 到 11 不可达:

点对 (i,j)(i,j) Dis(i,j)\mathrm{Dis}(i,j) Dis(i,j)+f\mathrm{Dis}(i,j)+f 异或完的 SS
(1,1)(1,1) 00 1000000000000000010000000000000000 1000000000000000010000000000000000
(1,2)(1,2) 11 1000000000000000110000000000000001 11
(2,1)(2,1) 101610^{16}(不可达) 2000000000000000020000000000000000 2000000000000000120000000000000001
(2,2)(2,2) 00 1000000000000000010000000000000000 2830042723378790528300427233787905

前两项只差最低位,异或后只剩一个 11;最后一步 20000000000000001⊕10000000000000000=2830042723378790520000000000000001 \oplus 10000000000000000 = 28300427233787905, 与样例输出一致。这也说明:可达与不可达的点对在异或里地位相同, 不要想着「先把不可达挑出来单独处理」。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:12
# update_at: 2026-10-07 15:12

import sys

INF = 10**16  # 不可达标记,与题面程序里的 f 同值;真实最短路的量级远小于它
MASK = (1 << 64) - 1  # C++ long long 的位宽,用来模拟它的溢出回绕
SIGN = 1 << 63        # 64 位整数的符号位

# 类型别名:邻接矩阵,Dist[i][j] 是 i 到 j 的当前最短距离(0 起下标)
type Dist = list[list[int]]


def wrap(x: int) -> int:
    """把结果折回 C++ long long 的 64 位有符号范围:题面程序用 ll 运算,Python 整数不溢出。"""
    x &= MASK
    return x - (1 << 64) if x >= SIGN else x


def relax_via(dis: Dist, k: int) -> None:
    """把中转点 k 放进允许集合:dis[i][j] 松弛到 min(dis[i][j], dis[i][k] + dis[k][j])。"""
    dk = dis[k]  # 第 k 行,本轮所有松弛都要用它
    # 只枚举 k 真正能到达的 j:边权可以为负,拿 dk[j] = INF 去加会得到
    # INF + 负数 < INF,等于把"不可达"当成一条超长的路写进 dis[i][j]
    reachable = [j for j, w in enumerate(dk) if w != INF]
    for row in dis:
        if row[k] == INF:
            continue  # 到不了中转点 k,这一轮 row 松弛不了任何点
        for j in reachable:
            nd = wrap(row[k] + dk[j])  # row[k] 不提前取:j == k 时这一格会被本循环改写
            if nd < row[j]:
                row[j] = nd


def floyd(dis: Dist) -> None:
    """就地求全源最短路:依次放开每个中转点,跑完 dis[i][j] 就是最短距离。"""
    for k in range(len(dis)):
        relax_via(dis, k)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    dis: Dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]  # Dis(i,i) = 0
    for _ in range(m):
        s, t, d = next(data) - 1, next(data) - 1, next(data)
        if d < dis[s][t]:
            dis[s][t] = d  # 有重边,只留最短的一条

    floyd(dis)

    # 照抄题面程序:逐对把 Dis(i,j) + f 异或进 S(不可达点对贡献 2f)
    S = 0
    for row in dis:
        for value in row:
            S ^= wrap(value + INF)
    print(S)


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 15:12
 * update_at: 2026-10-07 15:12
 */
// roj 1421 Floyd:读懂题面那段异或求和程序,先用 Floyd 求出全部点对最短路,
// 再照抄那段程序逐对异或。与 main.py 是同一算法。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 505;               // n <= 500,多开几位
const ll INF = 10000000000000000LL; // 不可达标记 1e16,与题面程序里的 f 同值

int n, m;
ll dis[MAXN][MAXN]; // dis[i][j] = i 到 j 的当前最短距离,不可达时为 INF

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) dis[i][j] = INF;
        dis[i][i] = 0; // 题面规定 Dis(i,i) = 0
    }
    for (int e = 1; e <= m; e++) {
        int s, t;
        ll d;
        scanf("%d %d %lld", &s, &t, &d);
        if (d < dis[s][t]) dis[s][t] = d; // 有重边,只留最短的一条
    }

    // Floyd:外层枚举中转点 k,内层尝试用 i->k->j 松弛 i->j
    for (int k = 1; k <= n; k++) {
        ll *dk = dis[k]; // 第 k 行,本轮所有松弛都要用它
        for (int i = 1; i <= n; i++) {
            ll *di = dis[i];
            if (di[k] == INF) continue; // 到不了中转点 k,这一轮 i 松弛不了任何点
            for (int j = 1; j <= n; j++) {
                // k 到不了 j 时 dk[j] = INF 必须先跳过:边权可以是负数,
                // 否则 INF + 负数 < INF,会把"不可达"当成一条超长的路写进 di[j]
                if (dk[j] == INF) continue;
                ll nd = di[k] + dk[j]; // di[k] 不提出循环:j == k 时这一格会被本循环改写
                if (nd < di[j]) di[j] = nd;
            }
        }
    }

    // 照抄题面程序:把所有点对的 Dis(i,j) + f 异或起来(不可达点对贡献 2f)
    ll S = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) S ^= dis[i][j] + INF;

    printf("%lld\n", S);
    return 0;
}

关于 main.py 里的 wrap:题面那段程序用 long long 运算,一旦某次加法溢出 64 位, C++ 会回绕而 Python 的大整数不会。按题面保证(无负环)数据不会溢出,wrap 就是恒等函数; 把它显式写出来,只是为了让 Python 版和 C++ 版在任何数据上都逐位一致 (本地随仓数据里确实混入了负环,与题面「保证没有负环」不符,此时判题答案正是 C++ 回绕后的结果)。

复杂度

  • 时间:Floyd 是三重循环,共 n3=5003=1.25×108n^3 = 500^3 = 1.25 \times 10^8 次内层松弛, 每次只做一次加法与一次比较,O(n3)O(n^3)。C++ 实测最慢一组(n=500n = 500,m=250000m = 250000) 耗时约 0.130.13 s,限时 10001000 ms 内非常安全。
  • 空间:邻接矩阵 n2n^2 个 long long,500×500×8B≈2500 \times 500 \times 8\text{B} \approx 2 MB, O(n2)O(n^2);实测峰值内存 8.4 MB,限 128 MB。
  • Python 版:算法完全相同,但 1.25×1081.25 \times 10^8 次内层松弛由解释器逐条执行, 实测最慢一组约 10 s,会 TLE。这是解释器常数问题,不是算法问题; 本题的正确提交语言是 C++,Python 版仅用于对照理解与对拍。

总结

  • 先读懂程序再动手:本题的题意藏在一段代码里,SS 是异或和而不是求和,读错就全错。 读出「异或」之后,剩下的就只是全源最短路。
  • 用约束反推算法:n⩽500n \leqslant 500 配上全源最短路需求,O(n3)O(n^3) 的 Floyd 是唯一顺手的选择; mm 再大也不影响 Floyd 的复杂度(边只在读入时用一次),负权边又排除了 Dijkstra。
  • 负权下 INF 是危险值:INF+负数<INF\text{INF} + \text{负数} < \text{INF} 会让「不可达」变成一条假路, 并且沿着中转点扩散到整张表。凡是「边权可为负 + 用 101610^{16} 之类大数当不可达标记」的题, 都必须显式判断两端可达再松弛,不能把标记值直接丢进加法。
  • 重边与自环:重边只留最短的一条;自环 s→ss \to s 长度为 00 时对 dis[s][s] = 0 无影响, 长度为负的自环就是负环,题面已保证不存在。