问个图论问题
查看原帖
问个图论问题
199750
试试事实上吗楼主2020/6/16 21:35

有一个有nn个点的环(n<=1e5)(n<=1e5),每个点有点权,边有边权。

现在删除环上的一条边。

定义两个点之间的距离为两点的点权和与删边后路径的边权和,现在希望求出删除某条边后使距离最大的两个点的距离最小。

求删边后距离的最小值。

正解好像是O(n)O(n)但我太菜想不出来

2020/6/16 21:35
加载中...