P1041 · OFFICIAL SOLUTION

P1041 我们最好的最短路官方题解

Gioush OJ · P1041 我们最好的最短路

我们最好的最短路

【题意简述】

给出一张 $n$ 个点、 $m$ 条边的连通无向图，满足 $m-n\leq 20$ 。多次询问两点之间的最短路。

【Hint】

【提示】

任取一棵生成树，非树边只有常数条。把所有非树边端点作为关键点，从每个关键点运行一次 Dijkstra。

【数据点 1∼21\sim 21∼2】

使用 Floyd 预处理任意两点之间的最短路。时间复杂度为 $\mathcal{O}(n^3+q)$ ，空间复杂度为 $\mathcal{O}(n^2)$ 。

【数据点 3∼43\sim 43∼4】

图是一棵树。倍增预处理最近公共祖先，并记录根到每个结点的距离 $d_u$ 。树上两点距离为

\operatorname{dist}_T(u,v)=d_u+d_v-2d_{\operatorname{LCA}(u,v)}.

【数据点 5∼65\sim 65∼6】

询问数较小时，可以对每次询问从起点运行 Dijkstra。时间复杂度为 $\mathcal{O}(qm\log n)$ 。

【正解】

从原图中任取一棵生成树 $T$ 。非树边数量为

m-(n-1)=m-n+1\leq 21.

把所有非树边的两个端点放入集合 $K$ ，则 $\lvert K\rvert\leq 42$ 。

先在生成树上倍增预处理最近公共祖先，从而支持树上距离 $\operatorname{dist}_T(u,v)$ 。再从每个关键点 $k\in K$ 出发，在原图上运行一次 Dijkstra，记到结点 $v$ 的最短距离为 $\operatorname{dist}_k(v)$ 。

对于询问 $(u,v)$ ，答案为

\min\left\{ \operatorname{dist}_T(u,v), \min_{k\in K}\bigl(\operatorname{dist}_k(u)+\operatorname{dist}_k(v)\bigr) \right\}.

若一条最短路不经过非树边，那么它完全位于生成树中，只能是树上 $u$ 到 $v$ 的唯一简单路径，第一项得到答案。

若一条最短路经过非树边，那么它必然经过某条非树边的端点 $k\in K$ 。沿最短路在 $k$ 处分开，有

\operatorname{dist}_k(u)+\operatorname{dist}_k(v) \leq \operatorname{dist}(u,v).

左侧本身对应一条从 $u$ 经过 $k$ 到 $v$ 的合法路线，又不可能小于全局最短路，所以该关键点给出的候选恰好等于答案。

【复杂度分析】

总时间复杂度为

\mathcal{O}\bigl(n\log n+\lvert K\rvert m\log n+q(\lvert K\rvert+\log n)\bigr),

空间复杂度为 $\mathcal{O}(n\log n+\lvert K\rvert n+m)$ 。边权与路径长度需要使用 long long。

【参考代码】

1#include <queue>2#include <vector>3#include <cstdio>4#include <cstring>5#include <algorithm>6#define MAXN 1000107#define MAXK 458using namespace std;9 10int c,n,m,q,In1,In2,In3,Head[MAXN],TreeHead[MAXN],Total=0,TreeTotal=0;11int SetFa[MAXN],Size[MAXN],Fa[MAXN][22],Dep[MAXN],Key[MAXK],cnt=0;12long long Dis[MAXN],Dist[MAXK][MAXN];13bool Mark[MAXN];14 15struct edge {16    int Ed,Next;17    long long Val;18}Edge[MAXN<<1],Tree[MAXN<<1];19 20void Edge_Add(int St,int Ed,int Val){Edge[++Total]={Ed,Head[St],Val};Head[St]=Total;}21void Tree_Add(int St,int Ed,int Val){Tree[++TreeTotal]={Ed,TreeHead[St],Val};TreeHead[St]=TreeTotal;}22int Find(int x){return SetFa[x]==x?x:SetFa[x]=Find(SetFa[x]);}23void Insert(int x){if (!Mark[x]) Mark[x]=1,Key[++cnt]=x;}24 25void Build() {26    queue <int> Q;27    Dep[1]=1;Q.push(1);28    while (Q.size()) {29        int Now=Q.front();Q.pop();30        for (int i=TreeHead[Now];i;i=Tree[i].Next) {31            int To=Tree[i].Ed;32            if (To==Fa[Now][0]) continue;33            Fa[To][0]=Now;Dep[To]=Dep[Now]+1;34            Dis[To]=Dis[Now]+Tree[i].Val;35            for (int j=1;j<=21;j++) Fa[To][j]=Fa[Fa[To][j-1]][j-1];36            Q.push(To);37        }38    }39}40 41int LCA(int x,int y) {42    if (Dep[x]<Dep[y]) swap(x,y);43    for (int i=21;i>=0;i--) if (Dep[Fa[x][i]]>=Dep[y]) x=Fa[x][i];44    if (x==y) return x;45    for (int i=21;i>=0;i--) {46        if (Fa[x][i]!=Fa[y][i]) x=Fa[x][i],y=Fa[y][i];47    }48    return Fa[x][0];49}50 51long long Query(int x,int y) {52    int lca=LCA(x,y);53    return Dis[x]+Dis[y]-2*Dis[lca];54}55 56priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> Q;57 58void Dijkstra(int x,int S) {59    memset(Dist[x],0x3f,sizeof(Dist[x]));60    Dist[x][S]=0;Q.emplace(0,S);61    while (Q.size()) {62        long long Value=Q.top().first;63        int Now=Q.top().second;Q.pop();64        if (Value!=Dist[x][Now]) continue;65        for (int i=Head[Now];i;i=Edge[i].Next) {66            int To=Edge[i].Ed;67            if (Dist[x][To]>Dist[x][Now]+Edge[i].Val) {68                Dist[x][To]=Dist[x][Now]+Edge[i].Val;69                Q.emplace(Dist[x][To],To);70            }71        }72    }73}74 75int main() {76#ifndef ONLINE_JUDGE77    freopen("shortest.in","r",stdin);78    freopen("shortest.out","w",stdout);79#endif80    scanf("%d",&c);81    scanf("%d%d",&n,&m);82    for (int i=1;i<=n;i++) SetFa[i]=i,Size[i]=1;83    for (int i=1;i<=m;i++) {84        scanf("%d%d%d",&In1,&In2,&In3);85        Edge_Add(In1,In2,In3);Edge_Add(In2,In1,In3);86        int x=Find(In1),y=Find(In2);87        if (x!=y) {88            if (Size[x]>Size[y]) swap(x,y);89            SetFa[x]=y;Size[y]+=Size[x];90            Tree_Add(In1,In2,In3);Tree_Add(In2,In1,In3);91        }92        else Insert(In1),Insert(In2);93    }94    Build();95    for (int i=1;i<=cnt;i++) Dijkstra(i,Key[i]);96    scanf("%d",&q);97    while (q-->0) {98        scanf("%d%d",&In1,&In2);99        long long Ans=Query(In1,In2);100        for (int i=1;i<=cnt;i++) Ans=min(Ans,Dist[i][In1]+Dist[i][In2]);101        printf("%lld\n",Ans);102    }103    return 0;104}