重要方盒

文章
3
资源
0
加入时间
2年10月21天

codeforce 449 B 最短路

codeforce 449 B题意: 一个无向图,给你两种边,一种边可以删除(全部从起点出发),问在不改变原来所有点最短路的情况下,能删最多多少条边。解: 由于可删边都从起点出发,松弛时候也不会返回起点,所以只需要建立从起点到另一点的单向边,然后进行一遍spfa,初始所有点的最短路的值,然后判断所有可删边,如果该边长比最短路的值长即可删,如果相等,再对到达的点进行判断,看能否由