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

· · 题解

这里提供一种 分治/倍增 的解法。

  首先我们可以想到一个fake的做法：直接建超级源汇然后跑最短路。这样只能拿到有向无环图的30pts，因为你没有办法处理“自己到自己”这种情况。

  然后我们很容易搞出一个O(N^2)的算法，就是枚举每个点然后跑一遍Dijkstra就可以了。

  我们考虑一下这个算法的瓶颈是什么？显然不是求最短路，而是枚举。 最后的答案肯定是点集中一个点ansS到ansT的最短路径，我们只要保证在枚举的时候，存在一个时刻，超级源点S连在ansS上并且ansT连在超级源点T上，而且这个枚举的复杂度可以接受就好了。

  我们思考一下能否在枚举的时候每次“倍增（分治）”。

  假设a数组为题目中给的点集，为了方便理解，我这里用线段树来解释，假设我们已经建好了a数组的线段树，第一次我们把a数组中，下标<=mid的都连到S，其余连到T：

  跑一边Dijkstra，然后把S和T反过来，S连右，T连左，再跑一遍Dijkstra。

  那么凡是ansS在a[1]-a[mid]/a[mid+1]-a[r]中，且ansT在a[mid+1]-a[r]/a[1]-a[mid]的情况都被我们一次统计了，剩下的就是ansT和ansS都在同一个线段里的情况了，那么我们第二次这么做：

  这样分治下去，只要logn次枚举就可以统计出答案，每次nlogn那么总复杂度就是O(Tnlog^2n)的，在O2（反正省选也有）下最慢的点在2s左右。

  为什么这么做不会漏掉答案呢？

  一句话:任意两个叶子在线段树上都有唯一的LCA，那么他们一定会在我们“分别连”这个LCA左右儿子的时候被枚举到。

  实际上这颗线段树根本不用建出来（似乎建出来连边可以优化到O(n)），直接暴力连边复杂度也是对的。代码实现的时候BFS分治并不好写，所以我写的是从叶子迭代上去，类似于倍增的方式(长得好像FFT...)。

  最优解是Dijkstra染色(O(Tnlogn))，但是我保证并不是每个人都会这东西，标算好像是拆二进制枚举，感觉虽然会好写一些，但是脑洞真的很大，像我这种人考试的时候肯定想不到，而这个类似于线段树的思路是比较native的，很容易想到，所以才有了这一篇题解，希望对大家有所帮助。

Code:

#include<cstdio>
#include<cmath>
#include<queue>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
static char buf[100000],*pa,*pd;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=110000,M=510000;
struct edge{
    int to,next;
    ll w;
}e[M];
int head[150000],tot;
void add(int x,int y,ll z){
    e[++tot].next=head[x];e[tot].to=y;head[x]=tot;e[tot].w=z;
}
int t,n,m,K,a[N];
const int S=0,T=N-1;
ll dis[N],ans;
#define re(a) memset((a),0,sizeof((a)))
void clear(){
    re(a);re(head);tot=0;
}
struct node{
    int u;
    ll udis;
};
bool operator < (node x,node y){
    return x.udis>y.udis;
}
priority_queue<node> q;
ll DJ(){
    memset(dis,127,sizeof(dis));
    dis[S]=0;
    q.push((node){S,0});
    register int i;
    while(!q.empty()){
        int u=q.top().u;ll udis=q.top().udis;q.pop();
        if(udis!=dis[u])continue;
        for(i=head[u];i;i=e[i].next)
            if(dis[u]+e[i].w<dis[e[i].to]){
                dis[e[i].to]=dis[u]+e[i].w;
                q.push((node){e[i].to,dis[e[i].to]});
            }
    } 
    return dis[T];
}
int past[150000];
void work(){
    register int i,j,l,r,mid;
    ans=(ll)pow(2,63)-10;
    memcpy(past,head,sizeof(past));
    for(mid=1;mid<=K;mid<<=1){
        for(l=0,r=mid<<1;l<=K;l+=r){
            for(j=l+1;j<=l+mid;j++)if(j<=K)add(S,a[j],0);
            for(j=l+mid+1;j<=l+r;j++)if(j<=K)add(a[j],T,0);
        }
        ans=min(ans,DJ());
        tot-=K;
        memcpy(head,past,sizeof(head));
        for(l=0,r=mid<<1;l<=K;l+=r){
            for(j=l+1;j<=l+mid;j++)if(j<=K)add(a[j],T,0);
            for(j=l+mid+1;j<=l+r;j++)if(j<=K)add(S,a[j],0);
        }
        ans=min(ans,DJ());
        tot-=K;
        memcpy(head,past,sizeof(head));
    }
    cout<<ans<<'\n';
}
int main(){
    t=read();
    register int i,x,y,z;
    while(t--){
        n=read();m=read();K=read();
        for(i=1;i<=m;i++){
            x=read();y=read();z=read();add(x,y,z);
        }
        for(i=1;i<=K;i++){
            a[i]=read();
        }
        work();
        clear();
    }
    return 0;
}