正确答案应该是多少
把 0 到 3 的所有路径都枚举一遍，取最短的。运行下面这段程序： #include <algorithm> #include <iostream> #include <queue> #include &
让它在反例上错一次
补全 dijkstra（照课本写法：弹出即定死），在那个有负权边的图上跑，输出它给 3 号的距离。 （本题用 g++ -std=c++17 -O0 编译。）
写一个暴力枚举当标尺
补全 go：把从 s 到 t 的所有不重复经过点的路径都走一遍，brute 取最小的总长。 （本题用 g++ -std=c++17 -O0 编译。）
对拍结果是不一致
Dijkstra 和暴力枚举都写好了，在那个有负权边的图上各求一次 0 到 3 的距离。补全暴力枚举里的 go，输出三样：Dijkstra 的答案 / 暴力的答案 / 两者是否相同（相同输出 结果一致，否则 结果不一致）。 （本题用 g++
Bellman-Ford 的做法
第 1 步：行是轮数，列是四个点 第 2 步：第 1 轮：所有边松弛一遍 第 3 步：第 2 轮：3 号改小了 第 4 步：第 3 轮：没有再变 第 5 步：不定死任何点，负边也扛得住 0 1 2 3 第1轮 第2轮 第3轮 0 2 5 5
为什么正好是 n-1 轮（C++）
Bellman-Ford 松弛 n-1 轮就够了，因为【0】。
怎么判断图里有负环（C++）
用 Bellman-Ford 判断负环的办法是【0】。
在反例上换成 Bellman-Ford
同一张有负权边的图，这次用 Bellman-Ford。运行下面这段程序： #include <algorithm> #include <iostream> #include <queue> #includ
两张图各有没有负环
一张是上一节那个有负权边的图，一张是 0→1:1、1→2:-1、2→1:-1（1 和 2 之间绕一圈是 -2）。运行下面这段程序： #include <algorithm> #include <iostream> #
写一个 Bellman-Ford
补全 bellman：把所有边松弛 n-1 轮。在那个有负权边的图上跑，输出整张距离表。 （本题用 g++ -std=c++17 -O0 编译。）