传送门
分析
好题，值得做一下 注意到m-n<=20这个条件 将原来的m条边看做（n-1）条树边，（m-n+1）条非树边 对于树边直接lca求距离。 由于非树边最多21条。 因此我们对这21条边连接的42个点都跑一次最短路来更新答案的最小值即可。 注意离散化，虽然点只有42个，但点的编号可能很大 注意数据范围，long long 类型的INF要开大一些，一般的调试方法，将题目中给出的小样例，调大其权值
代码
#include<bits/stdc++.h>
#define in read()
#define N 100009
#define ll long long
#define inf (1ll<<50)
using namespace std
;
inline int read(){
int ans
=0;
char ch
=getchar();
while(!isdigit(ch
))ch
=getchar();
while(isdigit(ch
))ans
=(ans
<<3)+(ans
<<1)+(ch
^48),ch
=getchar();
return ans
;
}
int n
,m
;
int nxt
[N
<<1],head
[N
],cnt
=1;
int fa
[N
][25],dep
[N
];
ll d
[50][N
],dtree
[N
];
int key
[N
<<1],num
=0;
bool is_tree
[N
<<1],vis
[N
];
struct egde
{
int u
,v
;
ll w
;
}E
[N
<<1];
void add(int x
,int y
,int z
){
nxt
[++cnt
]=head
[x
];head
[x
]=cnt
;E
[cnt
].v
=y
;E
[cnt
].w
=z
;E
[cnt
].u
=x
;
nxt
[++cnt
]=head
[y
];head
[y
]=cnt
;E
[cnt
].v
=x
;E
[cnt
].w
=z
;E
[cnt
].u
=y
;
}
void dfs1(int u
,int fu
){
fa
[u
][0]=fu
;dep
[u
]=dep
[fu
]+1;
for(int e
=head
[u
];e
;e
=nxt
[e
]){
int v
=E
[e
].v
;
if(v
==fu
||fa
[v
][0]) continue;
is_tree
[e
]=is_tree
[e
^1]=1;
dtree
[v
]=dtree
[u
]+E
[e
].w
;
dfs1(v
,u
);
}
}
void spfa(int S
){
queue
<int > q
;
int s
=key
[S
];
d
[S
][s
]=0;q
.push(s
);
while(!q
.empty()){
int u
=q
.front();q
.pop();vis
[u
]=0;
for(int e
=head
[u
];e
;e
=nxt
[e
]){
int v
=E
[e
].v
;
if(d
[S
][v
]>d
[S
][u
]+E
[e
].w
){
d
[S
][v
]=d
[S
][u
]+E
[e
].w
;
if(!vis
[v
]){
q
.push(v
);
vis
[v
]=1;
}
}
}
}
}
int getlca(int x
,int y
){
if(dep
[x
]<dep
[y
]) swap(x
,y
);
int i
;
for(i
=20;i
>=0;--i
) if(dep
[fa
[x
][i
]]>=dep
[y
]) x
=fa
[x
][i
];
if(x
==y
) return x
;
for(i
=20;i
>=0;--i
)
if(fa
[x
][i
]!=fa
[y
][i
]) x
=fa
[x
][i
],y
=fa
[y
][i
];
return fa
[x
][0];
}
int main(){
n
=in
;m
=in
;
int i
,j
,k
,u
,v
,w
;
for(int i
=1;i
<=44;++i
)
for(int j
=1;j
<=n
;++j
) d
[i
][j
]=inf
;
for(i
=1;i
<=m
;++i
){
u
=in
;v
=in
;w
=in
;
add(u
,v
,w
);
}
dfs1(1,n
+1);
for(i
=2;i
<=cnt
;i
+=2)
if(!is_tree
[i
])
key
[++num
]=E
[i
].u
,key
[++num
]=E
[i
].v
;
sort(key
+1,key
+num
+1);
int numm
=unique(key
+1,key
+num
+1)-key
-1;
for(i
=1;i
<=numm
;++i
){
spfa(i
);
}
for(j
=1;j
<=20;++j
)
for(i
=1;i
<=n
;++i
)
fa
[i
][j
]=fa
[fa
[i
][j
-1]][j
-1];
int q
;
q
=in
;
for(i
=1;i
<=q
;++i
){
u
=in
;v
=in
;
int lca
=getlca(u
,v
);
ll ans
=dtree
[u
]+dtree
[v
]-2*dtree
[lca
];
for(j
=1;j
<=numm
;++j
){
ans
=min(ans
,d
[j
][u
]+d
[j
][v
]);
}
cout
<<ans
<<'\n';
}
return 0;
}
转载请注明原文地址: https://www.6miu.com/read-4931661.html
