神仙题.
先考虑平方级别的暴力怎么做.
明显答案有单调性, 先二分 \(c\).
先最短路预处理 \(dis_u\) 表示 \(u\) 到离它最近的充电站的距离 (一开始把 \(1\) 到 \(k\) 全部丢到优先队列里就行了).
考虑当前站在 \(u\) 点上时, 剩余的电量是 \(x\). 注意到由于起点是充电站, 就一定有 \(x\le c-dis_u\)(考虑最后一个走到的充电站沿最短路走到这)
如果 \(x<dis_u\), 因为终点是充电站, 肯定不可能再到终点.
否则就可以走到最近的充电站再回来,\(x\) 就可以变成 \(c-dis_u\). 前面也推过不可能变得更大.
于是就可以直接 DFS 了.
放个代码
怎么搞快点?
由于走到 \(u\) 时要 \(x\ge dis_u\) 才有用, 所以考虑我们会走一条边 \((u,v,w)\), 当且仅当 \(c-dis_u-w\ge dis_v\), 即 \(dis_u+dis_v+w\le c\).
那么问题变成求一条从 \(a\) 到 \(b\) 的路径使得路径上每条边的 \(dis_u+dis_v+w\) 的最大值最小 (明显是满足条件的最小的 \(c\)).
还不会?
右转 NOIP2013 货车运输.
如果用最小生成树或者 Kruskal 重构树, 时间复杂度大概是 \(O((n+m)\log n+m\log m+m\log n+q\log n)\).(最短路 + 给边排序 + 求树 + LCA)
(顺便提个并查集的做法: 询问离线下来, 森林中每棵树的根记录这里面有哪些点. 使用按秩合并, 每个点至多被合并 \(\log\) 次.)
Kruskal 重构树的代码
来源: http://www.bubuko.com/infodetail-3301252.html