CodeForces 101808K (Another Shortest Path Problem)[LCA]

发表于 | 更新于 | | 阅读次数：

题目链接：http://codeforces.com/gym/101808/problem/K

这题第一眼看上去是树上最短路，但麻烦的是它有n条边不是树。这张图仅有一个环，我们尝试讨论特殊情况把它转化为树上最短路来做。
我们忽略环强行建树，设环上的两个点为X和Y，两点之间的边权为Z，任何两个点经过数根的路径的距离为f(a,b)，那么a和b之间的最短路一定等于min{f(a,b),f(a,X)+f(b,X),f(a,Y)+f(b,Y),f(a,X)+f(b,Y)+Z,f(a,Y)+f(b,x)+Z}

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
100
101
102
103
104
105
106
107
108
109
110
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=100009;
const int DEG=20;
typedef long long ll;

struct Edge {
    int to,w,next;
}edge[maxn*2];
int head[maxn],tot;
int X,Y,Z;
void addedge(int u,int v,int w) {
    edge[tot].to=v;
    edge[tot].w=w;
    edge[tot].next=head[u];
    head[u]=tot++;
}

int fa[maxn][DEG];
ll dis[maxn];
int deg[maxn];
bool vis[maxn];
void init() {
    tot=0;
    memset(head,-1,sizeof(head));
    X=Y=Z=0;
    memset(vis,0,sizeof(vis));
}
void BFS(int root) {
    queue<int> que;
    deg[root]=0;
    fa[root][0]=root;
    dis[root]=0;
    que.push(root);
    vis[root]=true;
    while(!que.empty()) {
        int tmp=que.front();
        que.pop();
        for(int i=1;i<DEG;i++) {
            fa[tmp][i]=fa[fa[tmp][i-1]][i-1];
        }
        for(int i=head[tmp];i!=-1;i=edge[i].next) {
            int v=edge[i].to;
            if(v==fa[tmp][0]) continue;
            if(vis[v]) {
                if(!X) {
                    X=tmp;
                    Y=v;
                    Z=edge[i].w;
                }
                continue;
            }
            deg[v]=deg[tmp]+1;
            fa[v][0]=tmp;
            dis[v]=dis[tmp]+edge[i].w;
            que.push(v);
            vis[v]=true;
        }
    }
}
int LCA(int u,int v) {
    if(deg[u]>deg[v]) swap(u,v);
    int hu=deg[u],hv=deg[v];
    int tu=u,tv=v;
    for(int det=hv-hu,i=0;det;det>>=1,i++)
        if(det&1)
            tv=fa[tv][i];
    if(tu==tv) return tu;
    for(int i=DEG-1;i>=0;i--) {
        if(fa[tu][i]==fa[tv][i])
            continue;
        tu=fa[tu][i];
        tv=fa[tv][i];
    }
    return fa[tu][0];
}
ll f(int x,int y) {
    return dis[x]-2*dis[LCA(x,y)]+dis[y];
}
ll solve(int x,int y) {
    ll ans=f(x,y);
    ans=min(ans,f(x,X)+f(y,X));
    ans=min(ans,f(x,Y)+f(y,Y));
    ans=min(ans,f(x,X)+f(y,Y)+Z);
    ans=min(ans,f(x,Y)+f(y,X)+Z);
    return ans;
}
int main() {
    int T;
    int n,q;
    int u,v,w;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&q);
        init();
        for(int i=1;i<=n;i++) {
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
            addedge(v,u,w);
        }
        BFS(1);
        for(int i=0;i<q;i++) {
            scanf("%d%d",&u,&v);
            printf("%I64d\n",solve(u,v));
        }
    }
}