Floyd

【题目描述】

给定一个 $n$ 个点 $m$ 条边的有向图。$Dis(a,b)$ 表示 $a$ 到 $b$ 的最短距离，如果 $a$ 无法到达 $b$，则 $Dis(a,b)=10^{16}$，规定 $Dis(a,a)=0$。

读懂以下程序，并输出 $S$。

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

【输入】

第一行两个整数 $n, m$，代表点数和边数；

接下来 $m$ 行，每行三个整数 $s, t, d$，代表从 $s$ 到 $t$ 有一条长度为 $d$ 的有向边。

【输出】

输出一个整数表示 $S$。

【输入样例】

2 3
1 2 1
1 2 3
2 2 0

【输出样例】

28300427233787905

【提示】

数据规模及约定：

$N \le 500$，$0 \le M \le 250000$，$1 \le S, T \le N$，$-10^9 \le D \le 10^9$。

保证没有负环。

题面来源：https://blog.csdn.net/lybc2019/article/details/128441961 （标题「1421：Floyd」，含完整题面、数据范围及样例） 交叉佐证：https://blog.csdn.net/hejx0412/article/details/122021862 （标题「1421：Floyd」，题目描述与输入输出格式一致） 说明：原站 ybt.ssoier.cn 1421 显示「题目正在建设中」，本题面据上述两篇网络题解重建；数据范围（N≤500、M≤250000、D∈[−10⁹,10⁹]、无负环）出自第一篇博客【提示】节原文，样例输出 28300427233787905 已用程序独立验证吻合（见 gen-report.md）。注：同章节 1419 SPFA / 1420 Dijkstra 与 1421 并非共享题面模板，1421 有独立题面（求异或和 S 的全源最短路）。