c/c++开发分享cf567E. President and Roads(最短路计数)

题意

题目链接

给出一张有向图,以及起点终点,判断每条边的状态:

是否一定在最短路上,是的话输出’yes’

如果不在最短路上,最少减去多少权值会使其在最短路上,如果减去后的权值(< 1),输出’no’,否则输出’can + 花费’

sol

考察对最短路的理解。

首先确定哪些边一定在最短路上,一个条件是 从起点到该点的最短路 + 边权 + 从该点到终点的最短路 = 从起点到终点的最短路

同时还要满足没有别的边可以代替这条边,可以用tarjan求一下桥。当然也可以直接用最短路条数判

这样的话正反跑一边dijkstra求出最短路以及最短路径的条数,判断一下即可

%ignore_pre_1%

(0)
上一篇 2022年9月13日 上午10:13
下一篇 2022年9月13日 上午10:25

相关推荐

发表回复

登录后才能评论