读懂题面的异或求和程序后,用 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
形式化题目
给定
要求输出
其中
把每一项拆开看:
正解
思路
第一步:那段程序在算什么。 题面给的是一段代码而不是一句话,先把它翻译成人话:
long long S, f = 1e16;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
S ^= Dis(i, j) + f;不是求和、不是取模、也不是最大值,而是把
第二步:为什么只能是 Floyd。 需要全源最短路,候选做法有三种,代入
| 做法 | 复杂度 | 代入规模 | 结论 |
|---|---|---|---|
| 以每个点为源跑堆优化 Dijkstra | 太慢;而且负权边根本不能直接进 Dijkstra | ||
| 以每个点为源跑 SPFA | 单次最坏 |
最坏 |
卡不住,随时被构造数据打崩 |
| Floyd | 可行,而且天然支持负权边(只要无负环) |
两个关键点:
第三步:Floyd 的循环不变式。 记 dis[i][j] 为「只允许把编号
每跑完一轮 dis[i][j] 就是真正的最短路。初始化很直接:dis[i][i] = 0(题面规定),其余为 dis[s][t] = min(dis[s][t], d),重边只留最短的一条。
第四步:本题唯一容易踩的坑——负权下 INF 不能直接参与比较。 很多人的 Floyd 模板写成
// 危险写法:非负权数据上没问题,本题会出错
if (dis[i][k] + dis[k][j] < dis[i][j]) dis[i][j] = dis[i][k] + dis[k][j];它默认「
于是「
if (dis[i][k] == INF) continue; // i 到不了中转点 k,本轮 i 松弛不了任何点
...
if (dis[k][j] == INF) continue; // k 到不了 j,这条 i->k->j 根本不存在第五步:拿样例走一遍。 样例是
| 点对 |
异或完的 |
||
|---|---|---|---|
前两项只差最低位,异或后只剩一个
代码
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++ 版(同一算法):
/**
* 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 是三重循环,共
次内层松弛, 每次只做一次加法与一次比较, 。C++ 实测最慢一组( , ) 耗时约 s,限时 ms 内非常安全。 - 空间:邻接矩阵
个 long long,MB, ;实测峰值内存 8.4 MB,限 128 MB。 - Python 版:算法完全相同,但
次内层松弛由解释器逐条执行, 实测最慢一组约 10 s,会 TLE。这是解释器常数问题,不是算法问题; 本题的正确提交语言是 C++,Python 版仅用于对照理解与对拍。
总结
- 先读懂程序再动手:本题的题意藏在一段代码里,
是异或和而不是求和,读错就全错。 读出「异或」之后,剩下的就只是全源最短路。 - 用约束反推算法:
配上全源最短路需求, 的 Floyd 是唯一顺手的选择; 再大也不影响 Floyd 的复杂度(边只在读入时用一次),负权边又排除了 Dijkstra。 - 负权下 INF 是危险值:
会让「不可达」变成一条假路, 并且沿着中转点扩散到整张表。凡是「边权可为负 + 用 之类大数当不可达标记」的题, 都必须显式判断两端可达再松弛,不能把标记值直接丢进加法。 - 重边与自环:重边只留最短的一条;自环
长度为 时对 dis[s][s] = 0无影响, 长度为负的自环就是负环,题面已保证不存在。