吉姆 102394 H

描述

一个无向连通图，每个点 \(u\) 有点权 \(w_u\)，处在 \(u\) 点时可以花费 \(w_u\) 的时间去任何一个距离 \(u\) 最短路径边数不超过 \(f_u\) 的点。

现在，从 \(1\) 号点出发，对于每个 \(1\le k\le n\)，求出 \(1\) 到 \(k\) 需要的最小时间。

• \(n\leq 200000\)
• \(m\leq n+50\)

解决方案

首先解决，对于 \(n\) 个点 \(m\) 条边且只有点权的图，怎么 \(O(n\log n+m)\) 求单源最短路。

考虑 Dijkstra 的时候，以 \(dis_i+w_i\) 为关键字建立小根堆，其中 \(dis_i\) 是起点到 \(i\) 的最短路，每次取出堆顶节点 \(u\)，扫描出边 \((u,v)\)，如果 \(dis_v\) 还没有被求出来，就直接用 \(dis_u+w_u\) 更新 \(dis_v\)。

这样做的好处是每个点只会被入堆一次。

回到本题，距 \(u\) 距离不超过 \(f_u\) 的点数是 \(O(n)\) 的，所以跑最短路的总边数是 \(O(n^2)\) 的，直接用上面的算法不可接受。

由于每个点只要入堆一次，所以对于当前堆顶节点 \(u\)，找出所有还未求出 \(dis\) 的距其不超过 \(f_u\) 的点 \(v\) 更新就可以保证更新的次数为 \(O(n)\) 次。

考虑输入的图是一棵树怎么做。

对于每个点，记录点分树上子其树内的点到它在原树上的距离。查询一个点 \(u\) 的出边时，在点分树上找到 \(u\) 自己和它的所有祖先构成的集合 \(S\)，对于 \(x\in S\)，找到 \(x\) 的点分树子树内和 \(x\) 在原树距离不超过 \(f_u-dis(u,x)\) 的未删除的点即可。

可以点分治的时候 BFS 求出按到 \(x\) 距离从小到大的序列，维护指针，每次询问向后找即可。

指针总的偏移量不超过 \(O(n\log n)\)，集合 \(S\) 的大小不超过 \(\log n\)。

这样对树就有了 \(O(n\log n)\) 的做法了。

考虑加入一些非树边如何做。

如果非树边 \((x,y)\) 会对 \((u,v)\) 间的最短距离产生影响，那么 \((u,v)\) 间的最短路径一定经过 \(x\) 和 \(y\)。

所以对于每条非树边，取出 \(x\) ，总共 \(m-n+1\) 个这样的点，以它为起点 BFS，类似地指针维护即可。

总的时间复杂度 \(O(n\log n+n(m-n))\)。

参考代码

Submission #265206778 - Codeforces