题解 P5304 【[GXOI/GZOI2019]旅行者】

~~我也很好奇大家的复杂度为什么多了一个$log$。。。~~ 一句话题意:有向图$G$中$|V| = n$,$|E| = m$,给定一个特殊点点集$S,|S| = k(p_1,p_2, ...,p_k)$ 求$min(dis(p_i,p_j)) (i ≠ j)$. 首先有一个很暴力的$O(Tnlognlogk)$的方法~~这也就是出题人开$5000ms$的原因~~: $i ≠ j$ 当且仅当$i$和$j$至少有一位二进制位不同。 枚举不同的二进制位,每次把$k$个点分成$S_0,S_1$两个集合跑$Dijsktra$ 求$log_2k$次最短路并取$min$. 然而这题确实有$O(Tnlogn)$的做法。 首先,我们求出$f[i],g[i]$为$i$到某个关键点/某个关键点到$i$的最短距离。 写成式子就是 $f[i] = min(dis_{min}(i,p_j))$ $g[i] = min(dis_{min}(p_j,i))$ 注意$dis_{min}(i,p_j)$和$dis_{min}(p_j,i)$并不是同一个东西,因为**这是一张有向图。** 同时我们求出$From[i],To[i]$表示$f[i],g[i]$中 $dis_{min}(i,p_j)$和$dis_{min}(p_j,i)$对应的$p_j$ 即$f[i]$的最短路走到了拿里,$g[i]$的最短路是从哪里来的。 上述内容只要做两次$Dijsktra$,一次在$G$上，一次在$G$的反图上。 复杂度$O(nlogn)$ 考虑枚举一条边$(u,v,w),$ 如果$From[u] ≠ To[v],$那么就用$g[u] + f[v] + w$来更新答案。 再枚举点$u,$ 如果$From[u] ≠ To[u],$那么就用$g[u] + f[u]$来更新答案。 做完了。 这样做为什么是对的呢？ 引用一下某神犇的解释： "不难证明，对于源点 $i$，由 $i$ 拓展的点 $j$ 以及与 $j$ 相邻且不由$i$ 拓展的点 $k$， 如果 $i$ 的最优路径从 $j$ 走到了 $k$，那么走到拓展 $k$ 的源点是最优的。因此这个做法是正确的。" 对于一条最短的路径$x -> y$,假设其路径上没有边$(u,v)$满足$From[u] ≠ x,To[v] ≠ y$ 很显然的一点就是$f[v] <= dis_{min}(v,y)$且$g[u] <= dis_{min}(x,u)$ 如果此时$From[v] ≠ To[u],$那么存在比$x->y$不劣的解被更新了，对$ans$没有影响。 如果$From[v]$和$To[u]$都$≠x,y$，那么如果它们相等， 令$z = From[v]$,说明$dis_{min}(z,v) + w + dis_{min}(u,x)$也可以更新$ans$, 且$dis_{min}(x,u) >= dis_{min}(z,u), dis_{min}(v,y) >= dis_{min}(v,z)$ 如果存在$>1$个这样的点$z$,那么一定有路径$z_1->z_2$比$x ->y$不劣且被更新到，对$ans$没有影响。 如果只存在一个这样的$z$,就回到了上面一种情况，要么$x->y$只有一条边(显然不可能) ，要么就一定有$(u,v)$满足$From[v] ≠ To[u].$ 再讨论$From[v] = To[u] = x/y$的情况。 由于路径长为正整数，所以如果$From[v] = To[u] = x/y$, 那么找到它在$x->y$中的前/后的任意一条边，一定有$From[v] ≠ To[u].$ 证毕。 那么代码实现也就很简单了。 ```cpp #include <bits/stdc++.h> #define LL long long using namespace std; inline LL read(){ LL x = 0,f = 1; char c = getchar(); while (c != EOF && !isdigit(c)) {if (c == '-') f = -1;c = getchar();} while (isdigit(c)) {x = x * 10 + c - '0';c = getchar();} return x * f; } inline void write(LL x){ if (x < 0) putchar('-'),x = -x; if (x > 9) write(x/10); putchar(x%10+'0'); } inline void writeln(LL x){ write(x),putchar('\n'); } const int N = 100005,M = 500005; int Fr[M<<2],To[M<<2],Ne[M<<2],Dis[M<<2],He1[N],He2[N],_k; inline void add(int *He,int x,int y,int z){ ++_k,Fr[_k] = x,To[_k] = y,Dis[_k] = z,Ne[_k] = He[x],He[x] = _k; } int T,n,m,k,p[N]; const LL INF = 1ll<<60; int f1[N],f2[N]; LL dis1[N],dis2[N]; struct Node{ int x; LL d; Node (int xx = 0,LL dd = 0){ x = xx,d = dd; } inline bool operator < (Node x) const{ return d > x.d; } }t; priority_queue<Node>Heap; void Dij_1(){ //dis1 : p[i] -> x int i; while (!Heap.empty()) Heap.pop(); for (i = 1; i <= n; ++i) dis1[i] = INF,f1[i] = -1; for (i = 1; i <= k; ++i) dis1[p[i]] = 0,f1[p[i]] = p[i],Heap.push(Node(p[i],0)); int p,x; while (!Heap.empty()){ t = Heap.top(); Heap.pop(); if (t.d == dis1[t.x]) for (p = He1[t.x]; p ; p = Ne[p]) if (dis1[To[p]] > dis1[t.x] + Dis[p]){ dis1[To[p]] = dis1[t.x] + Dis[p]; f1[To[p]] = f1[t.x]; Heap.push(Node(To[p],dis1[To[p]])); } } } void Dij_2(){ //dis2 : x -> p[i] int i; for (i = 1; i <= n; ++i) dis2[i] = INF,f2[i] = -1; for (i = 1; i <= k; ++i) dis2[p[i]] = 0,f2[p[i]] = p[i],Heap.push(Node(p[i],0)); int p,x; while (!Heap.empty()){ t = Heap.top(); Heap.pop(); if (t.d == dis2[t.x]) for (p = He2[t.x]; p ; p = Ne[p]) if (dis2[To[p]] > dis2[t.x] + Dis[p]){ dis2[To[p]] = dis2[t.x] + Dis[p]; f2[To[p]] = f2[t.x]; Heap.push(Node(To[p],dis2[To[p]])); } } } LL ans; int main(){ int i,u,v,w; T = read(); while (T--){ _k = 0; memset(He1,0,sizeof(He1)); memset(He2,0,sizeof(He2)); n = read(),m = read(),k = read(); while (m--){ u = read(),v = read(),w = read(); if (u^v) add(He1,u,v,w),add(He2,v,u,w); } for (i = 1; i <= k; ++i) p[i] = read(); Dij_1(); Dij_2(); ans = INF; for (i = 1; i <= n; ++i) if (f1[i] ^ f2[i]) ans = min(ans,dis1[i] + dis2[i]); for (i = 1; i <= _k; i += 2) if (f1[Fr[i]]^f2[To[i]]) ans = min(ans,dis1[Fr[i]] + dis2[To[i]] + Dis[i]); writeln(ans); } return 0; } ```