P9370 APIO2023 赛博乐园 / cyberland。
题目就是让我们求一个有各种优惠政策的单源点 \(0\)，单汇点 \(H\) 的最短路。优惠政策是：
- 到达能力为 \(2\) 的点，可以让之前走过的距离除以 \(2\)。
- 到达能力为 \(0\) 的点，可以让之前走过的距离直接变成 \(0\)。
有限制：不能经过 \(H\) 多次。那其实也就是说，\(H\) 只能作为答案路径的终点，不能作为路径的途经点。
优惠政策最短路，再加上 97 分中 \(K\) 的限制为 \(K \le 30\)，优惠政策能使用的次数很低。
上面加粗的两句正是分层图最短路的两条重要特征。于是想到建立 \(K\) 层的分层图，来解决“除以 \(2\)”这个优惠政策。
这里默认读者已经学会分层图，若不会，请先学习并完成分层图模板：JLOI2011 飞行路线。这里还有分层图题单，供读者练习。
原图为第 \(0\) 层图，总共建立 \(K +1\) 层图（编号 \(0 \sim K\)），第 \(p\) 层的点 \(u\) 代表之前使用优惠恰好 \(p\) 次，到达点 \(u\) 的状态。我们记其为 \((p, u)\)。设它的最短路为 \(\mathrm{dis}(p, u)\)。
最短路算法必须使用 dijkstra，用 spfa 虽然可以通过原题的数据，但复杂度是错的，讨论区中有 hack 数据。
定义 \(w(u, v)\) 为原图上 \(u\) 和 \(v\) 两点之间的边权。如果 \(u\)，\(v\) 两点之间没相连接的边则 \(w(u, v)\) 未定义。
思路一
首先想一下，到达能力为 \(0\) 的点可以清空最短路，那其实就相当于从这个点开始走。
因此，我们将所有能从 \(0\) 出发，不途径 \(H\) 到达的，能力同时为 \(0\) 的点看做源点，跑多源最短路即可。
那么能力为 \(0\) 就解决了，现在只需要解决能力 \(2\)。
考虑在 dijkstra 枚举出边时进行如下松弛：
- 尝试用 \(\mathrm{dis}(p, u) + w(u, v)\) 更新 \(\mathrm{dis}(p, v)\)。代表不使用优惠政策。
- 尝试用 \(\dfrac{\mathrm{dis}(p, u) + w(u, v)}2\) 更新 \(\mathrm{dis}(p + 1, v)\)。代表使用优惠政策。
同时注意 \(H\) 不能是途经点，因此 \(\mathrm{dis}(p, H)\) 强制不松弛其它点即可。
跑一个源点为 \((0, 0)\) 的单源最短路，然后取 \(\mathrm{dis}(0, H)\)，\(\mathrm{dis}(1, H)\)，\(\mathrm{dis}(2,H)\)……中的最小值，作为答案即可。
然而这种思路的问题在于，上面的第二种松弛并不是平凡的最短路松弛，违背了 dijkstra 的正确性。
但是只要进行一步修改，上面的思路就是正确的了：
考虑朴素的 dijkstra 的优先队列，我们会优先取出 \(\mathrm{dis}\) 最小的 \((p, u)\)。而这里我们修改成：
- 对于 不同层 的两个点 \((p, u)\) 和 \((q, v)\)，不妨令 \(p <q\)，则 \((p, u)\) 更优先，不管最短路；
- 对于 同层 的两个点 \((p, u)\) 和 \((p, v)\)，则取 \(\mathrm{dis}\) 更小的更优先。
每次取最优先的开始松弛就一定没有问题。解释一下原因：
分层图是单向导通的，高层点的最短路一定不会影响低层点。
观察全局上优先队列取出的过程，大体上是优先低层，然后再优先低距离。
也就是说，在第 \(0\) 层图上，只有从点 \(0\) 出发能到达（中途不经过 \(H\)）的所有点，都当过一次队头，并松弛一遍其它点之后，才会开始处理第 \(1\) 层图的点。
我们称 dijkstra 的过程中，层号为 \(p\) 的点充当队头的阶段为第 \(p\) 阶段。那么整个 dijkstra 过程就是 \(k + 1\) 个阶段的综合：第 \(0\) 阶段，第 \(1\) 阶段，……，第 \(k\) 阶段。
那么在第 \(0\) 阶段之后，第 \(0\) 层的所有点的最短路都已经被计算好，并且已经为真实值了（原因就是高层最短路不会影响低层）。此时，目前第 \(1\) 层的点 \((1, u)\) 最短路的值是：只途径 \(0\) 层的所有点，到达 \((1, u)\) 这个点的距离的一半。
先不进行第 \(1\) 阶段，来看第 \(1\) 阶段之前，我们只看第 \(1\) 层的点，会发现只有这个变化：
一般的单源最短路，在初始时，都是源点距离为 \(0\)，而其它点距离为 \(+\infty\)。
而这里的单源最短路，若干点的距离已知，而其它点的距离为 \(+\infty\)。
会发现这种变化是不影响 dijkstra 的。可以联想一下，将这些距离已知的点 \((1, u)\)，新建一个虚点，对虚点向 \((1, u)\) 连一条权值为 \(\mathrm{dis}(1, u)\) 的边。然后对虚点为源点，跑单源最短路，那么第一步松弛的结果就是目前第 \(1\) 层点的状态。
显然 dijkstra 经过一次松弛之后仍然是正确的，所以该算法是没问题的。
上面我们阐述了从第 \(0\) 阶段到第 \(1\) 阶段的正确性，事实上，在第 \(p\) 个阶段结束后，前 \(p\) 层的最短路都已经确定，而第 \(p + 1\) 层的最短路可以看作若干个点的距离已经已知的最短路，所以第 \(p +1\) 个阶段仍然是正确的。
因此所有阶段都是正确的，算法正确。
这里设边数为小写 \(m\)，复杂度为 \(\Theta(mK \log mK)\)。
100 分做法
上面的做法是 97 分的，\(K \le 30\)。考虑 100 分的 \(K \le 10^6\)。
我们发现，事实上用一些次优惠政策之后，最短路会变的很低，远远低于精度。
具体来说，本题中最短路最大不超过边数乘边权最大值，即 \(10^{14}\)。只需让这个数除以 \(70\) 次 \(2\) 就可以掉到 \(10^{-7}\) 以下（\(8 \times 10^{-8}\)）。
也就意味着使用 \(70\) 次优惠政策之后，再优惠只可能会让最短路再少个 \(10^{-7}\) 以下。
而题目要求精度 \(10^{-6}\) 就够了，所以求出的最短路比真实最短路多个 \(10^{-7}\) 以下是可以接受的。
因此，令 \(k = \min(K, 70)\)，然后再按照 97 分做法做即可。复杂度 \(\Theta(mk \log mk)\)。
当然，如果你当心上面的 \(10^{-7}\) 误差能累计到影响答案（虽然感觉上不可以），把阈值设的高一点也没问题。
#include <bits/stdc++.h>
const int N = (int)1e5 + 5;
const int K = 75;
typedef std :: pair <int, int> pii;
struct node {
int p;
int u;
double dis;
const bool operator < (const node b) const {
if (this -> p != b.p)
return this -> p > b.p;
return this -> dis > b.dis;
}
};
std :: vector <pii> G[N];
double dis[K][N];
std :: bitset <N> vis[K];
std :: bitset <N> con;
inline void init(int n, int k) {
con.reset();
for (int u = 0; u < n; ++u)
G[u].clear();
for (int p = 0; p <= k; ++p)
vis[p].reset();
for (int p = 0; p <= k; ++p)
for (int u = 0; u < n; ++u)
dis[p][u] = 1e17;
}
void dfs(int u, int t) {
con.set(u);
for (pii e : G[u]) {
int v = e.first;
if (!con[v] && v != t)
dfs(v, t);
}
}
double solve(int n, int m, int k, int t, std :: vector <int> us, std :: vector <int> vs, std :: vector <int> wei, std :: vector <int> a) {
if (k > 70)
k = 70;
init(n, k);
for (int i = 0; i < m; ++i) {
int u = us[i], v = vs[i], w = wei[i];
G[u].push_back({v, w});
G[v].push_back({u, w});
}
dfs(0, t);
std :: priority_queue <node> q;
for (int u = 0; u < n; ++u) {
if (con[u] && (a[u] == 0 || u == 0)) {
dis[0][u] = 0;
q.push({0, u, 0});
}
}
while (!q.empty()) {
node now = q.top();
q.pop();
int u = now.u, p = now.p;
if (vis[p][u] || u == t)
continue;
vis[p].set(u);
for (pii e : G[u]) {
int v = e.first, w = e.second;
if (dis[p][v] > dis[p][u] + w) {
dis[p][v] = dis[p][u] + w;
if (!vis[p][v])
q.push({p, v, dis[p][v]});
}
if (a[v] == 2 && p < k) {
if (dis[p + 1][v] > (dis[p][u] + w) / 2) {
dis[p + 1][v] = (dis[p][u] + w) / 2;
if (!vis[p + 1][v])
q.push({p + 1, v, dis[p + 1][v]});
}
}
}
}
double ans = DBL_MAX;
for (int p = 0; p <= k; ++p)
ans = std :: min(ans, dis[p][t]);
if (ans > 1e15)
return -1;
return ans;
}
思路二
如果你想不到修改堆排序方式，还有一种思路，我们只需要对原题进行转化并进行合理地分层之后，套一个裸 dijkstra 就可以解决。
考虑建立反图（虽然无向图的反图和原图是一样的），观察反的最短路径上，优惠政策的含义：
- 原先遇到能力为 \(0\) 的点，会把当前距离设置为 \(0\)；
- 那么现在遇到能力为 \(0\) 的点，相当于让之后走过的所有边权都变成 \(0\)。
- 原先遇到能力为 \(2\) 的点，会把当前距离减半；
- 那么现在遇到能力为 \(2\) 的点，相当于让之后走过的所有边权都变成原来的一半。
我们发现，直接让第 \(p\) 层上 \(u\) 和 \(v\) 之间的边权为原图上 \(u\) 和 \(v\) 之间边权的 \(\dfrac{1}{2^p}\)，就能满足能力为 \(2\) 的点；至于能力为 \(0\) 的点，我们可以新建一层 \(K + 1\) 层，让这一层内 \(u\) 和 \(v\) 之间的边权都改成 \(0\)。然后让所有 \(a[v] = 0\) 的 \((p, v)\) 直接单向导通到 \(K + 1\) 层即可。
这样以来，裸的 dijkstra 就可以解决问题。此时汇点是 \(H\)，源点是 \(0\)。
同时注意一下不能途径 \(H\) 的问题。思路一中，我们是允许某个点松弛 \((p, H)\) 的，只是不允许 \((p, H)\) 松弛别人而已；思路二中我们是从 \(H\) 出发，这里我们不能允许任意一个点松弛 \((p, H)\)。
#include <bits/stdc++.h>
const int N = (int)1e5 + 5;
const int K = 75;
typedef std :: pair <int, int> pii;
struct node {
int p;
int u;
double dis;
const bool operator < (const node b) const {
return this -> dis > b.dis;
}
};
std :: vector <pii> G[N];
double dis[K][N];
std :: bitset <N> vis[K];
double val[K];
inline void init(int n, int k) {
val[0] = 1;
for (int i = 1; i <= k; ++i)
val[i] = val[i - 1] / 2;
val[k + 1] = 0;
for (int u = 0; u < n; ++u)
G[u].clear();
for (int p = 0; p <= k + 1; ++p)
vis[p].reset();
for (int p = 0; p <= k + 1; ++p)
for (int u = 0; u < n; ++u)
dis[p][u] = 1e17;
}
double solve(int n, int m, int k, int t, std :: vector <int> us, std :: vector <int> vs, std :: vector <int> wei, std :: vector <int> a) {
if (k > 70)
k = 70;
init(n, k);
for (int i = 0; i < m; ++i) {
int u = us[i], v = vs[i], w = wei[i];
G[u].push_back({v, w});
G[v].push_back({u, w});
}
std :: priority_queue <node> q;
dis[0][t] = 0;
q.push({0, t, 0});
while (!q.empty()) {
node now = q.top();
q.pop();
int u = now.u, p = now.p;
if (vis[p][u])
continue;
vis[p].set(u);
for (pii e : G[u]) {
int v = e.first, w = e.second;
if (v == t)
continue;// 这里阻止松弛的方式和思路一不同，原理已经解释
if (a[v] == 0) {
if (dis[k + 1][v] > dis[p][u] + w * val[p]) {
dis[k + 1][v] = dis[p][u] + w * val[p];
if (!vis[k + 1][v])
q.push({k + 1, v, dis[k + 1][v]});
}
continue;
}
if (dis[p][v] > dis[p][u] + w * val[p]) {
dis[p][v] = dis[p][u] + w * val[p];
if (!vis[p][v])
q.push({p, v, dis[p][v]});
}
if (a[v] == 2 && p < k) {
if (dis[p + 1][v] > dis[p][u] + w * val[p]) {
dis[p + 1][v] = dis[p][u] + w * val[p];
if (!vis[p + 1][v])
q.push({p + 1, v, dis[p + 1][v]});
}
}
}
}
double ans = DBL_MAX;
for (int p = 0; p <= k + 1; ++p)
ans = std :: min(ans, dis[p][0]);
if (ans > 1e15)
return -1;
return ans;
}