题解 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的原因:

枚举不同的二进制位,每次把$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].

证毕。

那么代码实现也就很简单了。

#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;
}