2021ZJCPC-D题题解

xia0ji233

同时作为一个 $ACMer$，也想分享一下上次咱省赛一道难题的题解，目前网上并找不到很好的题解，代码是我阅读过其它标程之后自己写的，并且给出了自认为已经十分详细的解析了。先说一下这题比赛的情况吧，基本上呢，银奖中等偏上的队伍都是做出来了的。

那我们就看看这题吧。

题目简介

什么思路在题目名字这里就一目了然了，那自然是最短路径。

而当我一眼扫过去看到这个数据量的时候瞬间惊呆。$1≤n≤100000，1≤m≤200000$，不仅如此，还有 $q$ 次询问最短路径，$q≤200000$ 当时一看，这玩你妈。给一个点都勉强能过了，这有这么多点，如果按照常规思路，一次单源最短路径复杂度 $nlog_2n$ 然后 $q$ 次询问，总复杂度就是 $qnlog_2n$ 全部以最大值带进去妥妥的超时。所以当时比赛的时候看到这个题目是直接放弃了的，而且英文不好的我留下了悔恨的眼泪。

题目分析

但是它还有一个条件，那就是，直接相连的两个点当中，其中一个点的编号一定是另一个点的二进制前缀，这就说明了一点，$2$ 它一定不会跟 $3,6,12……$ 等点连接起来的，因为它们的前缀是 $11_{2}$，而 $2_{10}$ 是 $10_{2}$ 开头的，那么这样的话我们就可以构造一棵 $tire$ 树。像这样子。

可以很明显的看出来是一个完全二叉树，这里我们假设往左子树走二进制右添一个 $0$，向左走二进制右添一个 $1$。那你可能会想，这明明边的范围是比点多的，怎么可能是一棵树。没错，但是我们看看，它能不能边横向添加？答案当然是否定的，因为一个得是另一个的前缀，同层次的话二进制位数相同，但是实际值不同，因此不可能满足这个条件。那么我们看看能不能连到其它不是我的祖先的节点呢？答案当然还是否定的，因为我简历的 $tire$ 就是根据二进制后面添 $0$ 还是添 $1$ 来确定分支的，如果你都不是由我在后面添 $0$ 或者是添 $1$ 得到的那你就不可能是我的前缀，也不是我的孙子节点。

当然在图中 $1$ 和 $4$ 是可以直接相连的，虽然越级但是满足条件。所以它严格意义上来说不是树，但它怎么当成树呢？如果我把一个节点两个直接相连的子图当成子树，问题就解决了。因为两个子图之间肯定没有线连接，这个在刚刚已经证明过了。

对于每一个节点，我们都去寻找它祖先的最短路径。因为一个节点最多有 $log_2n$ 个祖先，所以跑一下最短路算法问题还是不大的。我们定义 $dis[i][k]$ 为节点 $i$ 到达往上 $k$ 个祖先的最短路径。那么对于任意两点的最短路径，我只需要寻找它们的最近公共祖先，然后答案就是 $a$ 到最近公共祖先的最短路加上 $b$ 到最近公共祖先的最短路。当然我们还有一个情况得考虑，因为 $dis[i][k]$ 的定义仅仅是到它祖先的最短路径，而不是到这个节点的最短路径。因此它祖先的祖先可能有更优的路线。

就比如这样一个图，图中我把关键数据标注出来了，无关数据没有标注。

如果说我要求 $8$ 和 $11$ 的最短路，按照我刚刚的定义很容易算的出来，它们的 $LCA$ 是 $2$，然后 $8$ 和 $11$ 到 $2$ 的最短路径都是 $2$，所以我算出来 $8$ 到 $11$ 的最短路径是 $4$，但是显然这里还有一个更优的解，那就是 $8\to1\to11$ 这样才只有 $2$ 的距离。但是最优的路线只可能存在于它的祖先上面了，其它地方不可能有。因此我们在用刚刚那个算法的时候还得兼顾一下查找 $LCA$ 的祖先的答案。

这样子的话，假如我们能在规定时间内预处理完数据，那么我们每次查询的时间复杂度就只有 $O(log_2n)$ 了，也不会超时。那么我们看看怎么去预处理这个 $dis$ 数组。

我们只需要以每一个节点为根节点，和根节点的子节点作为一张图去跑单源最短路即可。对于 $1$ 来说，它的复杂度会是 $O(nlog_2n)$ ，每向下走一层，根节点数量翻倍，子节点数量减半。第二层中，总共复杂度将是 $O(2 \times \frac{n}{2}log_2\frac{n}{2})$ 这么算下来这一层接近 $O(nlog_2n)$ ，此后每一层都接近 $O(nlog_2n)$。它一共有几层呢？$log_2n$层。所以预处理的时间复杂度仅仅只有 $O(n(log_2n)^2)$ 这个时间复杂度是完全不会超时的。

我们肯定还是选择 $dijsktra$ 算法作为我们的单源最短路算法，加上一个优先队列优化，单源最短路需要每一个点给一个 $d$ 数组标记所有节点到源点的最短路，但是这样空间会炸。所以我们每次跑最短路空间得共用，如何保证他们不会串呢？用标记数组。比如我在以 $1$ 为根节点的时候，我就给标记打上 $1$，当我要更新 $d$ 里面的值的时候我先比较一下上一个使用 $d$ 数组的时候这个标记是否为我当前的根节点，如果是则更新，如果不是，则先初始化为一个很大的值。一般情况下我们选择 $INF=0x3f3f3f3f3f3f3f3f$ 因为这样不容易溢出，也能表示无穷大。

但是呢，想想 $dijsktra$ 算法还有什么需要注意的？那就是每次选完一个点的时候，它不会再被更新，这个时候我需要再打上一个标记，防止它被其它相连的边重复更新答案。一般情况下我们是选择 $0,1$ 的，但是这里我们要一起用我们就选择根节点的值呗，如果当前根节点和这个值不相等说明这个点没有被添加，那就添加并将标记更新为当前的根节点。

那么思路清晰了我们就开写。

循序渐进

首先开这么几个数组

• $d[i]$ 表示 $i$ 点到当前根节点的最短路径
• $vis1[i]$ 表示 $i$ 节点上一次被 $vis1[i]$ 节点标记为已经添加最短路的答案
• $vis2[i]$ 表示 $i$ 节点的 $d[i]$ 上一次是在以 $vis2[i]$ 为根节点时更新的

图的话我们采用经典链式前向星存储，优先队列我们存储这么两个信息：

1. x节点的最短路径
2. x节点

我们肯定每次是以最路径为关键字进行小根堆构造的，这样保证每次 $pop$ 出来的答案都是当前未被添加的节点中最小的那个答案。

于是我们不难写出以下代码。

void dijkstra(int root){
    p.push({0,root});//先把根节点丢进去
    d[root]=0;//自己到自己肯定就是0
    vis2[root]=root;//自己这个答案肯定要被标记，防止下面找到被初始化，当然你如果严格规定所得节点必须<root也没关系，因为下面会被初始化为INF。
    while(!p.empty()){
        auto x=p.top();
        p.pop();
        int point=x.second;//当前找到了一个距离最短的节点
        if(vis1[point]==root)continue;//如果已经被添加过了那么就不做以下处理
        vis1[point]=root;//把这个节点标记为已经添加进了答案中
        dis[point][cal_c(point,root)]=d[point];//更新答案，这里的cal_c用于判断root在point的第几个祖先，我们设父亲为第一个祖先。
        for(int i=head[point];i;i=edge[i].next){//更新所有与之相连的点的答案
            int to=edge[i].to;
            if(to<root)continue;//基本判断防止找到root的父亲
            if(vis2[to]!=root){//如果不是root说明上一次使用d[to]数组的还是上一次……啊不，是没用过d[to]这个值，所以要被初始化为一个无穷大
                d[to]=INF;
                vis2[to]=root;//标记
            } 
            if(d[point]+edge[i].w<d[to]){//单源最短路判断
                d[to]=d[point]+edge[i].w;
                p.push({d[to],to});//push进优先队列中
            }
        }
    }
}

那么结合代码中你的注释相信你已经不难理解这个 $dijsktra$ 算法了。

我们再看看查询这部分的代码应该怎么写，无非就是先求出 $LCA$ ，然后循环 $LCA$ 以及 $LCA$ 祖先的答案。

while(q--){
    int x,y;
    cin>>x>>y;
    int lca=LCA(x,y);//先求最近公共祖先
    int lx=cal_c(x,lca),ly=cal_c(y,lca);//算出他们在那个点的第几个祖先
    int ans=INF;
    while(lca){
        ans=min(ans,dis[x][lx]+dis[y][ly]);//寻找最小值
        lx++,ly++;//每次往上看看那个祖先
        lca>>=1;//完全二叉树怎么找自己的父亲，这个不难吧？
    }
    if(ans==INF)printf("-1\n");
    else printf("%lld\n",ans);//输出答案
}

重要的部分写完了之后那么整个程序就呼之欲出了，但是一定得注意，不开 $long long$ 见祖宗哦。

然后还有一点就是，既然你开了 $long long$ 一定不要忘了 $inf$ ，不要漏写一半，不然真到比赛要么哭罚时，要么哭整整一题了，不管前者后者，都是很伤的，建议先记在心里。

标程

#include<bits/stdc++.h>
#define maxn 100005
#define INF 0x3f3f3f3f3f3f3f3f
#define int long long
using namespace std;
typedef pair<int,int> P;
struct eee{
    int next;
    int to;
    int w;
}edge[maxn<<2];
int head[maxn],dis[maxn][30],cnt,n,m;
int vis1[maxn];
int vis2[maxn];
int d[maxn];
priority_queue<P,vector<P>,greater<P> > p;
int cal_c(int child,int ancestor){
    int cnt=0;
    while(child>ancestor){
        cnt++;
        child>>=1;
    }
    return cnt;
}

void add(int x,int y,int w){
    edge[++cnt].next=head[x];
    edge[cnt].to=y;
    edge[cnt].w=w;
    head[x]=cnt;
} 

void dijkstra(int root){
    p.push({0,root});
    d[root]=0;
    vis2[root]=root;
    while(!p.empty()){
        auto x=p.top();
        p.pop();
        int point=x.second;
        if(vis1[point]==root)continue;
        vis1[point]=root;
        dis[point][cal_c(point,root)]=d[point];
        for(int i=head[point];i;i=edge[i].next){
            int to=edge[i].to;
            if(to<root)continue;

            if(vis2[to]!=root){
                d[to]=INF;
                vis2[to]=root;
            } 
            if(d[point]+edge[i].w<d[to]){
                d[to]=d[point]+edge[i].w;
                p.push({d[to],to});
            }
        }
    }
}
int LCA(int a,int b){
    while(a!=b){
        if(a>b)a>>=1;
        else b>>=1;
    }
    return a;
}

signed main(){
    //freopen("1.in","r",stdin);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,w;
        cin>>x>>y>>w;
        add(x,y,w);
        add(y,x,w);
    }

    memset(dis,0x3f,sizeof(dis)); 
    for(int i=1;i<=n;i++){
        dijkstra(i);
    }
    int q;
    cin>>q;
    while(q--){
        int x,y;
        cin>>x>>y;
        int lca=LCA(x,y);
        int lx=cal_c(x,lca),ly=cal_c(y,lca);
        int ans=INF;
        while(lca){
            ans=min(ans,dis[x][lx]+dis[y][ly]);
            lx++,ly++;
            lca>>=1;
        }
        if(ans==INF)printf("-1\n");
        else printf("%lld\n",ans);
    }
    return 0;
}

蒟蒻的提交记录。

测评网站

至于踩的那几个坑嘛，就是 $long long$ 的问题了，然后还有一点就是输入的问题，这个具体看我上一篇博客吧，我到现在还没太弄懂，不过至少能注意规避的技巧了：那就是千万别在开

ios::sync_with_stdio(false);

的情况下用 $scanf$ 去读取 $long long$ 数据，不然你会怀疑人生。

希望这次省赛能超越上次的自己吧，$xia0ji233,fighting！！！$