最短路

圆方树

题目链接

建出圆方树,圆点到方点的距离为它爬到这个方点在圆方树的父亲的距离,圆点到圆点之间的距离为边长。

两个点的最短路长度分两种情况讨论:

$Lca$为圆点,那么就是树上距离

$Lca$为方点,那两个点就都爬到这个方点对应的环上,再求一个环上距离

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/*
>Author: zxy_hhhh
>blog: zxy-hhhh.cn
>date: 2019/01/09
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<vector>
#include<map>
#define rep(x,a,b) for (int x=int(a);x<=(int)(b);x++)
#define drp(x,a,b) for (int x=int(a);x>=(int)(b);x--)
#define cross(x,a) for (int x=hd[a];x;x=nx[x])
#define ll long long
using namespace std;
inline ll rd()
{
ll _x=0;int _ch=getchar(),_f=1;
for(;!isdigit(_ch)&&(_ch!='-')&&(_ch!=EOF);_ch=getchar());
if (_ch=='-'){_f=0;_ch=getchar();}
for(;isdigit(_ch);_ch=getchar()) _x=_x*10+_ch-'0';
return _f?_x:-_x;
}
void write(ll _x){if (_x>=10) write(_x/10),putchar(_x%10+'0'); else putchar(_x+'0'); }
inline void wrt(ll _x,char _p){if (_x<0) putchar('-'),_x=-_x; write(_x); if (_p) putchar(_p);}
#define maxn 500005
#define maxm 500005
int tot,n,m,a[maxn],Q;
#define len(x,y) (mp[make_pair(x,y)])
map< pair<int,int>,int > mp;
namespace Tree {
int nx[maxn<<1],to[maxn<<1],hd[maxn<<1],cnt;
inline void add(int u,int v) {
//wrt(u,' '),wrt(v,'\n');
nx[++cnt]=hd[u],to[cnt]=v,hd[u]=cnt;
}
ll sum1[maxn<<1],sum2[maxn<<1],sum[maxn<<1],Dep[maxn<<1];
int f[maxn<<1][20],dep[maxn<<1];
void dfs(int u) {
dep[u]=dep[f[u][0]]+1,Dep[u]=Dep[f[u][0]]+sum[u];
//wrt(u,' '),wrt(sum[u],' '),wrt(Dep[u],'\n');
rep(i,1,16) f[u][i]=f[f[u][i-1]][i-1];
cross(i,u) f[to[i]][0]=u,dfs(to[i]);
}
inline int _lca(int u,int v) {
if (dep[u]<dep[v]) swap(u,v);
drp(i,16,0)
if (dep[f[u][i]]>=dep[v]) u=f[u][i];
if (u==v) return u;
drp(i,16,0)
if (f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
return f[u][0];
}
inline int jump(int u,int v) {
drp(i,16,0)
if (dep[f[u][i]]>dep[v]) u=f[u][i];
return u;
}
inline ll dis(int x,int y) {
int Lca=_lca(x,y);
if (Lca<=n) return (Dep[x]+Dep[y]-2*Dep[Lca]);
else {
int xx=jump(x,Lca),yy=jump(y,Lca);
if (sum1[xx]<sum1[yy]) swap(xx,yy);
return Dep[x]-Dep[xx]+Dep[y]-Dep[yy]+
min(sum1[xx]-sum1[yy],sum2[xx]+sum1[yy]);
}
}
}
int dfn[maxn],low[maxn],id;
int sta[maxn],top;
int nx[maxm],to[maxm],val[maxm],hd[maxn],cnt;
int ans;
inline void add(int u,int v,int L) {
nx[++cnt]=hd[u],val[cnt]=L,to[cnt]=v,hd[u]=cnt;
}
void tarjan(int u,int fa) {
dfn[u]=low[u]=++id;
sta[++top]=u;
for(int i=hd[u];i;i=nx[i]) if (to[i]!=fa) {
int v=to[i];
if (!dfn[v]) {
tarjan(v,u);
low[u]=min(low[u],low[v]);
if (low[v]>dfn[u]) {
Tree::add(u,v),top--;
Tree::sum[v]=val[i];
}
else if (low[v]==dfn[u]) {
tot++;
int x=top;
while(sta[x]!=v) Tree::add(n+tot,sta[x]),x--;
Tree::add(n+tot,sta[x]);
Tree::add(u,n+tot);
Tree::sum1[sta[x]]=val[i];
rep(j,x+1,top)
Tree::sum1[sta[j]]=
Tree::sum1[sta[j-1]]+len(sta[j-1],sta[j]);
Tree::sum2[sta[top]]=len(sta[top],u);
Tree::sum[sta[top]]=
min(Tree::sum1[sta[top]],Tree::sum2[sta[top]]);
drp(j,top-1,x){
Tree::sum2[sta[j]]=
Tree::sum2[sta[j+1]]+len(sta[j+1],sta[j]);
Tree::sum[sta[j]]=
min(Tree::sum1[sta[j]],Tree::sum2[sta[j]]);
}
top=x-1;
}
}
else low[u]=min(low[u],dfn[v]);
}
}
int main()
{
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
n=rd(),m=rd();Q=rd();
rep(i,1,m) {
int x=rd(),y=rd(),z=rd();
add(x,y,z),add(y,x,z);
len(x,y)=len(y,x)=z;
}
tarjan(1,0);Tree::dfs(1);
rep(i,1,Q){
int x=rd(),y=rd();
wrt(Tree::dis(x,y),'\n');
}
}
avatar
多项式