CF1051F The Shortest Statement

· · 题解

题解

首先明确，肯定不能跑 q 次 dijkstra，因为几乎没有优化空间。

那该怎么做？数据范围其实有提示，当 m=n-1 时，即本身图就是一棵树的情况，答案直接就是树上两点之间的距离，可以用 LCA 进行 O(\log n) 求解。

考虑环套树的情况，相当于在一棵确定好的树上加上一些非树边。先预处理求出这棵树的倍增数组和每个节点到根节点的距离。

此时非树边对于答案有影响，当且仅当新的最短路径经过这条非树边，也经过这条非树边的端点。所以找出所有非树边的端点，以每个端点为起点跑 dijkstra ，预处理求出最多 k（这里 k 的含义在下面解释）个最短路的 dis 数组。

对于每个询问 u,v，答案为 \max\{dep_u+dep_v-2dep_{lca},dis(i,u)+dis(i,v)\}，其中 i 为每组端点预处理出的最短路的编号。

一个细节

关于 k：对于每一条非树边，选取其中的一个端点即可（因为只要经过这条非树边即可），相比取两个端点要节省一倍的时间。因此 k 的取值范围应该是 k=m-n，即 k\le 40。

然而由于不是特别好实现（偷懒），本人代码中还是把每条非树边的两个端点都记录了，因此数组也开了两倍（100）。

代码

代码看着很长，其实全是板子。


#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f,N = 1e5+10;
#define ll long long
#define pr pair<ll,int>
#define MP make_pair
inline ll read()
{
    ll ret=0;char ch=' ',c=getchar();
    while(!(c>='0'&&c<='9')) ch=c,c=getchar();
    while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ch=='-'?-ret:ret;
}
int n,m,Q;
int ecnt=-1,head[N];
ll dis[100][N],cnt,pot[100];
int f[20][N],dep[N];
bool vis[N],pass[N],used[N];
struct edge
{
    int nxt,to,w;
}a[(N<<1)+100];
inline void add(int x,int y,int w)
{
    a[++ecnt]=(edge){head[x],y,w};
    head[x]=ecnt;
}
inline void dijk(int st,const int id)
{
    priority_queue<pr,vector<pr>,greater<pr> >q;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++) dis[id][i]=1e18;
    dis[id][st]=0ll;
    q.push(MP(0,st));
    while(!q.empty())
    {
        int u=q.top().second; q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];~i;i=a[i].nxt)
        {
            int v=a[i].to;
            if(dis[id][v]>dis[id][u]+a[i].w)
            {
                dis[id][v]=dis[id][u]+a[i].w;
                q.push(MP(dis[id][v],v));
            }
        }
    }
    return;
}
void dfs(int u,int fa)
{
    pass[u]=1;
    for(int i=1;i<=19;i++) f[i][u]=f[i-1][f[i-1][u]];
    for(int i=head[u];~i;i=a[i].nxt)
    {
        int v=a[i].to;
        if(v==fa) continue;
        if(pass[v]) 
        {
            if(!used[v]) pot[++cnt]=v,used[v]=1;
            continue;
        }
        dis[0][v]=dis[0][u]+a[i].w;
        dep[v]=dep[u]+1;
        f[0][v]=u;
        dfs(v,u);
    }
}
inline int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=19;i>=0;i--)
        if(dep[f[i][x]]>=dep[y]&&f[i][x]) x=f[i][x];
    if(x==y) return x;
    for(int i=19;i>=0;i--)
        if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];
    return f[0][x];
}
inline ll Dis(int x,int y){return dis[0][x]+dis[0][y]-(dis[0][lca(x,y)]<<1);}
int main()
{
    //freopen("path.in","r",stdin);
    //freopen("path.out","w",stdout);
    memset(head,-1,sizeof(head));
    n=read(),m=read();
    for(int i=1;i<=m;i++) 
    {
        int u=read(),v=read(),w=read();
        add(u,v,w),add(v,u,w);
    }
    dfs(1,0);
    for(int i=1;i<=cnt;i++) dijk(pot[i],i); 
    Q=read();
    while(Q--)
    {
        int u=read(),v=read();
        ll ans=Dis(u,v);
    //  printf("ans=%lld\n",ans);
        for(int i=1;i<=cnt;i++) 
            ans=min(ans,dis[i][u]+dis[i][v]);
        printf("%lld\n",ans);
    }
    return 0;
}