今天来复盘一下上次省赛考到的题目，异常地折磨人。

先说一下这题比赛的情况吧，基本上呢，银奖中等偏上的队伍都是做出来了的。

那我们就看看这题吧。

题目简介

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

而当我一眼扫过去看到这个数据量的时候瞬间惊呆。\(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\) 出来的答案都是当前未被添加的节点中最小的那个答案。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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\) 祖先的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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\) ，不要漏写一半，不然真到比赛要么哭罚时，要么哭整整一题了，不管前者后者，都是很伤的，建议先记在心里。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#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\) 的问题了，然后还有一点就是输入的问题，这个具体看我上一篇博客吧，我到现在还没太弄懂，不过至少能注意规避的技巧了：那就是千万别在开

1
ios::sync_with_stdio(false);

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

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