鸡你太美
by dfgfdfg @ 2022-10-27 17:38:03
@[dfgfdfg](/user/853509) 你他妈的不会说话把手剁下来连着键盘送给山区小朋友行吗？
by Register_int @ 2022-10-27 17:45:26
@[Retr0_Gu](/user/535407) 可以用dij 吧，我这么写过了
by 阴语飞 @ 2022-11-01 16:08:34
@[阴语飞](/user/297103) 用的二分还是分层图
by Retr0_Gu @ 2022-11-01 18:58:13
@[Retr0_Gu](/user/535407) 分层图一次 二分+分层图一次（第一次提交这样搞的过了，看题解分层图就没必要二分了，又把二分去了单独交了一次分层图）都是dij
by 阴语飞 @ 2022-11-01 19:17:43
但是分层图dij 更新需要取max而不是dis[k]=dis[x]+len
by 阴语飞 @ 2022-11-01 19:18:47
如果不能用dij有可能是因为有后效性，如果用spfa迭代几次可能会可以
by 966123anyunchuan @ 2022-11-03 22:24:12
考古+实践证明可以dij
by w9095 @ 2023-03-03 19:14:08
可以用的，如果把这题往动态规划想（f[u][j]表示 1 号点到 u 号点，使用了 j 次免费升级的机会后，路径上花费的最大值的最小值）
这题dij和spfa在处理后效性这个问题上有区别的：
+ spfa是通过迭代多次计算，把“答案收敛出来”
+ dij是用了这道题的单调特性，求的是路径上最大花费的最小值，那我们就把 1 到 u 的距离定义为“1 到 u 的路径中的最大花费”，如果我们能求出距离的最小值（即最短路），就能解决这个问题
这个“距离”也是有单调性的：由于边权非负，所以就代表着 u 去扩展 v 时，1 到 v 的路径中的最大花费只可能变大，所以当前队列中最小的那个点所代表的状态一定是一个最优状态（最短的状态，最大花费最小的状态）
不好理解的话，可以这样想：以1为起点开始扩展距离后，选取队列中距离最小的那个，假设为 i 点,由于边权非负，那么能保证此时到 i 点的距离是全局最小的（即不会再被更新到了），就能把i点确定下来，去扩展其他点
再说的抽象点：
+ spfa 是在图上乱搞，多次迭代出结果
+ dij 是在有单调性的图上，利用单调性确定一个特殊的序列，按照这个序列进行扩展能保证正确性
个人理解哈，不对请指出
by KKKZOZ @ 2023-05-05 11:41:15
可以用
by Austra @ 2023-08-24 16:23:43