题目大意： 有一张 \(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#include #include #define maxn 100010#define maxm 500010int 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;}