floyd——最短路里玩最花的
dij——跑得很快
spfa——差分约束&费用流
01bfs——边权只有两个时候最快
求最小环
首先floyd中\(f[i][j][k]\)代表从i到j中间只经过编号小于等于k的节点的最小值。那么我们可以想到一个环满足i-j的优弧（类似这么叫），然后剩下一个点编号大于k，直接加上边权即可。正确性是因为这是最优化问题，一个环上必定会有一个编号最大的点，答案就在这时候更新
分治
floyd的k的顺序是可以随便取的，所以可以分治。
百度地图的实时路况
要求的是全源最短路分别不走1-n的路径长度之和。删去一个贡献非常麻烦，并且我们发现有非常多贡献重复计算。考虑分治，和这题有点像，我们用类似线段树的方式。现在做到l-r代表全源最短路没有l-r时的样子，然后我们可以利用这个答案求出l-mid和mid+1-r的答案。具体而言，我们现在往下传l-mid的时候就将mid+1-r加入。但此时我们发现空间不够。我们发现只需记录线段树高的f数组就可以了，因为我们用的是dfs。
CF1196F
这题是全源最短路，同时边权都为正所以有很好的性质。我们删掉边权排名>=k的边，发现只剩下了400条边，然后直接\(n^3\)暴力floyd即可
P1811CF59E
三元关系不好处理，考虑将它们变成二元关系。具体而言，我们将边映射到一些标号上，然后这个三元关系就变成二元关系了。然后我们对边重新建图，发现边可能达到\(n^2\)级别，于是我们就不把边建出来。我们只是遍历一下，用map大力存一下。下次用map的时候记得重载下比较的运算符，不然会寄掉