牛客第三场提高组模拟赛T2题解
队除我炸
队里除了我都炸了
\[n,m \leq 5\times 10^5,q \leq 10^5,c_i\leq 600, 0<w_i,l_i,r_i < 10^9\]
首先不考虑 w（每条边的难度）的数据范围，我们可以得到以下的做法。
预处理:
用 spfa 求出 dis[i]，表示：从 x 到每一个点的路径上，最大难度的最小值
用 addp[i] （一个 vector）存储：牛半仙的困难接受程度从 i-1 增加到 i 的时候，他能见到的新的妹子们。
将 i 号节点 push 到 addp[dis[i]] 里。
计算...
