POJ2253最短路、最大权值最小
給出n个点的坐标,问点1到点2的所有路径中,经过的最大边的最小值可以是多少。其实这种最小化最大值的题,用二分+dj应该没问题,但是其实还有更简单的方法,只需要改变松弛操作即可。
最短路经典松弛操作:
1 | if (dis[v] > dis[u] + w) |
我们从本质出发,为什么这样更新呢?因为我们求最短路时最后想要的是最小的总dis。回到这题,我们最后想要的每条路径上所有小段的dis中的最小值。那么只需改变松弛操作为:
1 | if (dis[v] > max(dis[u] , w)) |
另外,这题n=200的数据范围,可以用Floyd写,更简单。Dijkstra代码
:
1 |
|