部分零碎知识点总结

判断一条边是不是在最短路上

2019多校 day1 path

记d（a，b）为点a到点b的最短路，则满足d（1，n）=d(1,a)+w(a,b)+d(b,n) 说明ab在最短路上，可以转换为最小割，转化为最大流 O（nm） 玄学效率跑1e4