交付之前必须验什么（C++）
把一个最短路或 MST 的解交出去，必须先验【0】。
五项一起对得上吗
运行下面这段程序： #include <algorithm> #include <iostream> #include <queue> #include <set> #include <
第一步最短路和路径
最终作品第一步：补全 dijkstra 和 back_track，输出 0 到 4 的最短总长和那条路径（路径用 - 连）。 （本题用 g++ -std=c++17 -O0 编译。）
第二步负权上换算法
在那个有负权边的图上，用 Dijkstra 和 Bellman-Ford 各求一次 0 到 3。补全 bellman，输出三样：Dijkstra 的答案 / Bellman-Ford 的答案 / 是否相同。 （本题用 g++ -std=c+
第三步两种 MST 互相印证
补全 prim 和 same_set，在同一组边上和 Kruskal 各求一次。输出三样：Kruskal 总长 / Prim 总长 / 边集是否相同。 （本题用 g++ -std=c++17 -O0 编译。）
第四步拆掉一条边试试
补全 kruskal 的选边循环和 without。分别拆掉 2-4（最贵，权重 9）和 0-2（最便宜，权重 1），各重新算一次最小总长，两个数拼起来输出（拆最贵的在前）。 （本题用 g++ -std=c++17 -O0 编译。）
交付导航加联网一起验收
这是这条路线的最终作品。其余函数都已写好，补全 has_neg_cycle、same_set、without 三个函数，一次验完五条：① 0 到 4 的最短总长是 6，路径是 0-1-3-4；② 负权图上 Dijkstra 给 5、Bell
十万个点该用哪种写法
十万个点、二十万条边的图求单源最短路，C++ 里应该用【0】。
补写 Kruskal
场景：实验机上 ~/work/sp/mst.cpp 读入一张无向图，要输出最小生成树的总长（图不连通就输出 -1），可 kruskal 还没写。 任务：补全 kruskal（并查集已经写好）。make 编译，./mst < sampl
十万个点的最短路
场景：~/work/sp/fast.cpp 用「每轮扫一遍找最近的点」的 O(n²) 写法求最短路。结果是对的，可十万个点时要跑很久。 任务：改写成小根堆的 Dijkstra，让十万个点、十二万条边在 3 秒内算完，输出格式不变。make