「思维+Floyed」AtCoder Beginner Contest 243 E – Edge Deletion Solution

题目传送门

题意：给定一个无向有权图，问最少保留哪些边使图的连通性和多源最短路径的性质保持不变。

先用Floyed做一遍最短路，考虑求有用边的数量。
若f[i][j]不存在有f[i][j]=f[i][k]+f[k][j]则这条边是有用的，也可以说是这条边不能被其他边来优化掉。
Tips：转移后的边是一定会被其他边表示的，也就是说原本不存在的边可以一起放进去考虑且一定不会被当成有用边。