如果你知道了 \(ans\)，那么把所有边的 \(x\) 调成 \(ans\) 一定不劣。
我们可以二分 \(ans\)，然后再将每条边的边权设为 \(a_ians + b_i\)，对于每个点跑最短路即可，但是你发现这样复杂度是 \(O(nm \log n \log V)\) 的，但由于 \(V\) 要取实数，所以其实 \(V\) 是 \(10^{16}\) 这个级别的，完全过不去。
再优化相当违反信息论，并没有可以利用的性质以及更为先进的做法，完全无法优化这个过程。
实际上，对于多元素同问题二分我们有经典处理手法，我们拆开对于每个元素做二分，先随机打乱点的排列，每次二分求出目前答案 \(ans'\)，我们检测一下 \(ans' + eps\) 是否可行再二分，看上去时间复杂度相当随机。实际上，进行二分的点的个数是 \(O(\log n)\) 级别的，因为这等价于随机排列前缀最大值个数（这也就是为什么要加 \(eps\)），再加上对于每个点都检测一遍的复杂度，实际复杂度为 \(O(nm \log n + m \log^2 n \log V)\)。
这种 trick 被 yzj 称为随机二分，他靠这个在省选考场上多拿了大几十分。