526互联

hszxoj 货车运输

发布时间 2023-12-18 21:47:06作者: 卡布叻_周深

题目链接： hszxoj 货车运输

题目描述与思路

  • 简化题目：
    求 \(x\)到 \(y\) 两点间路径的边权最小值的最大值
  • 与之前的最短路最大的不同是这道题是多源最短路，那么 \(spfa\) 就废了，\(Floyd\) 定会 \(TLE\) 所以就需要用新的算法。
  • 用 \(lca\) 一定是在树上的，但明显这玩意他既有环又有森林，直接用就会 \(RE\)