Codeforces

Luogu

分析

注意到 $m-n\leq 20$ ,所以我们随便拿一棵生成树出来,那么还会有至多 $21$ 条非树边。

那么 $u$ 到 $v$ 的最短路只有至多 $22$ 种可能:不经过任何一条非树边(或者说在树上),或者经过某一条非树边。我们只要对这些情况取个 $\min$ 即可。

树上最短路很好算,预处理到根的路径长度,用 LCA 算一下即可。

考虑后面那部分怎么算。对于每个是非树边的端点的点,求出从它出发的最短路。那么对于一条非树边 $(u,v,w)$,经过它的从 $x$ 到 $y$ 的最短路就是 $\min\left\{dis_{x,u}+w+dis_{v,y},dis_{x,v}+w+dis_{u,y}\right\}$ 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m;

struct sedge { int u,v,w; } se[N];
int in[N],tot=0;

int rt[N];
inline int find(int x) { return x==rt[x]?x:rt[x]=find(rt[x]); }

struct edge { int v,w,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}

int f[17][N],dep[N],sum[N];
inline void dfs(int u,int fa) {
    dep[u]=dep[fa]+1,f[0][u]=fa;
    for (re int i=1;i<17;++i) f[i][u]=f[i-1][f[i-1][u]];
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        if (!in[(i+1)/2]||v==fa) continue;
        sum[v]=sum[u]+w,dfs(v,u);
    }
}
inline int getlca(int u,int v) {
    if (dep[u]<dep[v]) swap(u,v);
    for (re int i=16;~i;--i)
        if (dep[f[i][u]]>dep[v]) u=f[i][u];
    if (dep[u]!=dep[v]) u=f[0][u];
    for (re int i=16;~i;--i)
        if (f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v];
    if (u!=v) u=f[0][u];
    return u;
}

struct node { int u,d; };
bool operator <(node a,node b) { return a.d>b.d; }
int dis[2][22][N];
inline void dijkstra(int s,int x,int y) {
    memset(dis[x][y],0x3f,sizeof(dis[x][y])),dis[x][y][s]=0;
    priority_queue<node> Q; Q.push((node){s,0});
    while (!Q.empty()) {
        int u=Q.top().u,d=Q.top().d; Q.pop();
        if (d!=dis[x][y][u]) continue;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (d+w<dis[x][y][v])
                dis[x][y][v]=d+w,Q.push((node){v,d+w});
        }
    }
}

signed main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        se[i]=(sedge){read(),read(),read()};
        addEdge(se[i].u,se[i].v,se[i].w);
        addEdge(se[i].v,se[i].u,se[i].w);
    }
    for (re int i=1;i<=n;++i) rt[i]=i;
    for (re int i=1;i<=m;++i) {
        int p=find(se[i].u),q=find(se[i].v);
        if (p^q) in[i]=1,rt[p]=q;
    }
    dfs(1,0);
    for (re int i=1;i<=m;++i) {
        if (in[i]) continue;
        se[++tot]=se[i];
        dijkstra(se[i].u,0,tot),dijkstra(se[i].v,1,tot);
    }
    int Q=read();
    while (Q--) {
        int u=read(),v=read(),t=getlca(u,v);
        int ans=sum[u]+sum[v]-(sum[t]<<1);
        for (re int i=1;i<=tot;++i)
            ans=min(ans,min(dis[0][i][u]+se[i].w+dis[1][i][v],
                            dis[0][i][v]+se[i].w+dis[1][i][u]));
        printf("%I64d\n",ans);
    }
    return 0;
}
最后修改:2019 年 10 月 14 日 04 : 38 PM