题目大意： 有一张 \(n(n\leqslant10^5)\) 个点 \(m(m\leqslant5\times10^5)\) 条边的有向有正权图，有\(k(2\leqslant k\leqslant n)\)个关键点。问图中最近的两个关键点的距离。多组数据。
题解： 有两种方法。
可对\(k\)个关键点二进制分组，可以知道\(x\)与\(y\)不同至少满足二进制上有一位不同，每次按二进制中的一位分成两组，，建一个虚点连向所有的源点，跑 \(dijkstra\) ，总共跑 \(\log_2n\) 次。复杂度 \(O(n\log_2^2n)\) 。代码我没写
-
令 \(F_i\) 表示可以走到第\(i\)个点的最近关键点，\(f_i\) 为 \(dis_{F_i,i}\) ， \(T_i\) 表示第\(i\)个点可以走到的最近关键点，\(t_i\) 为 \(dis_{i.T_i}\) 。由题解得，枚举一条边 \((u,v,w)\) ，若 \(F_u\not=T_v\) ，那么用 \(f_u+w+t_v\) 更新答案。这些数组可以在正反图上跑以所有关键点为源点的最短路径得到。接下来证明这样为什么是对的。
很显然可以证明，若最短路径为 \(x\to y\) ，其中边 \((u,v,w)\) 在这条路径上且 \(F_u\not=T_v\) ，那么 \(F_u=x,T_v=y\) （假定最短路径只有一条），则 \(f_u+w+t_v=ans\) 。也就是只要证明\(x\to y\)的路径上至少有一条边满足\(F_u\not=T_v\)
采用反证的方法。比如一张图如下，其中\(1\to n\)为最短路径，方点为关键点，设边权均为\(w\)
graph LR;
A[1]
B((2))
C((3))
D((n-1))
E[n]
A--A-->B
B--B-->C
C-.-D
D--Z-->E对于边\(A\)来说，\(F_u=1,T_v=n\)，要破坏，因为\(F_u\)无法改变，只能改变\(T_v\)，可以连一条\(2\to 1\)的边，边权小于\(w\)，那么边\(A\)就无法对答案产生贡献。再考虑边\(B\)，\(F_u=1,T_v=n\)，要破坏，有两种方法，一种是连一条\(n\to 2\)的边权小于\(w\)的边，另一种是连一条\(3\to 1\)的边权小于\(w\)的边。由于第一种方案会产生一条\(n\to 2\to 1\)的更短的路径，所以排去，只能用第二种。以此类推，最后会连一条\(n\to 1\)的边导致出现了更短的路径。与原来的假设矛盾。故原命题成立
卡点： 无
C++ Code：
#include <iostream>
#include <algorithm>
#include <cstring>
#define maxn 100010
#define maxm 500010
int cnt, head[maxn], _head[maxn];
struct Edge {
int to, nxt, w;
} e[maxm], _e[maxm];
inline void addedge(int a, int b, int c) {
e[++cnt] = (Edge) {b, head[a], c}; head[a] = cnt;
_e[cnt] = (Edge) {a, _head[b], c}; _head[b] = cnt;
}
int Tim, n, m, k;
int To[maxn], _To[maxn];
long long dis[maxn], _dis[maxn];
bool mar[maxn];
namespace Graph {
int V[maxn << 2];
long long *Dis;
inline int getmin(int a, int b) { return Dis[a] < Dis[b] ? a : b; }
void modify(int rt, int l, int r, int p, int num) {
if (l == r) {
V[rt] = num;
return ;
}
const int mid = l + r >> 1;
if (p <= mid) modify(rt << 1, l, mid, p, num);
else modify(rt << 1 | 1, mid + 1, r, p, num);
V[rt] = getmin(V[rt << 1], V[rt << 1 | 1]);
}
void dijkstra(int *head, Edge *e, int *To, long long *dis) {
const int SZ = maxn << 3;
memset(dis, 0x3f, SZ);
Dis = dis;
memset(V, 0, sizeof V);
for (int i = 1; i <= n; ++i) To[i] = i;
for (int i = 1; i <= n; ++i) if (mar[i]) {
dis[i] = 0;
modify(1, 1, n, i, i);
}
for (int Tim = n; Tim; --Tim) {
int u = V[1];
modify(1, 1, n, u, 0);
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] > dis[u] + e[i].w) {
dis[v] = dis[u] + e[i].w;
To[v] = To[u];
modify(1, 1, n, v, v);
}
}
}
}
}
using Graph::dijkstra;
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
std::cin >> Tim;
while (Tim --> 0) {
std::cin >> n >> m >> k;
for (int i = 0, a, b, c; i < m; ++i) {
std::cin >> a >> b >> c;
addedge(a, b, c);
}
memset(mar, false, sizeof mar);
for (int i = 0, x; i < k; ++i) std::cin >> x, mar[x] = true;
dijkstra(_head, _e, To, dis);
dijkstra(head, e, _To, _dis);
long long ans = 0x3f3f3f3f3f3f3f3f;
for (int i = 1, u, v; i <= m; ++i) {
u = _e[i].to, v = e[i].to;
if (_To[u] != To[v]) ans = std::min(ans, _dis[u] + e[i].w + dis[v]);
}
std::cout << ans << '\n';
if (Tim) {
memset(head, 0, sizeof head);
memset(_head, 0, sizeof _head);
cnt = 0;
}
}
return 0;
}