|
链接：https://ac.nowcoder.com/acm/challenge/terminal
来源：牛客网
题目描述
给一个连通图，每次询问两点间最短路。每条边的长度都是1。
输入描述:
第一行两个整数n和m，表示图的点数和边数（1≤ n≤ 100000, 1≤ m≤ n+100）。
接下来m行每行两个整数a和b，表示一条边（1≤ a, b≤ n）。保证没有自环和重边。保证图连通。
接下来一个整数q表示询问的个数（1≤ q≤ 100000）。
接下来q行每行两个整数a和b表示询问a和b之间的最短路。
输出描述:
每个询问输出一行表示答案。
示例1
输入
复制
4 5
1 2
2 3
1 4
4 3
2 4
4
1 4
1 2
2 4
1 3
输出
复制
1
1
1
2
因为数据量大，常用的多源最短路floyd肯定超时。由题目条件可知：最多有100个环。那么对于环的部分我们用dij，或者是简单bfs。而树上的就用LCA即可。然后取最小。思路很好。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
inline void scan_d(int &ret)
{
char c;
ret = 0;
while ((c = getchar()) < '0' || c > '9');
while (c >= '0' && c <= '9')
{
ret = ret * 10 + (c - '0'), c = getchar();
}
}
const int MAXN=100005;
vector<int> G[MAXN];
int N,M,Q;
/****树链剖分求LCA****/
int sz[MAXN];
int son[MAXN];
int top[MAXN];
int dep[MAXN];
int pre[MAXN];
void dfs1(int u, int fa)
{
pre[u]=fa;
sz[u]=1;
int& maxs = son[u]=-1;
dep[u] = dep[fa] + 1;
for(int i=0;i<G[u].size();i++)
{
int v = G[u][i];
if (v == fa)
continue;
dfs1(v, u);
sz[u]+=sz[v];
if(maxs==-1||sz[v]>sz[maxs])
maxs=v;
}
}
void dfs2(int u,int tp){
top[u]=tp;
if(son[u]!=-1)
dfs2(son[u],tp);
for(int i=0;i<G[u].size();i++)
{
int v = G[u][i];
if (v == pre[u])
continue;
if(v!=son[u])
dfs2(v,v);
}
}
void lca_init()
{
dep[0] = 0;
dfs1(1,0);
dfs2(1,0);
}
int LCA(int u, int v)
{
int uu = top[u], vv = top[v];
while (uu != vv) {
if (dep[uu] < dep[vv]) {
swap(uu, vv);
swap(u, v);
}
u = pre[uu]; uu = top[u];
}
if (dep[u] < dep[v])
swap(u, v);
return v;
}
/****LCA****/
int fa[MAXN];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int dis[105][MAXN];
int cnt=0;
bool in[MAXN];
queue<int> que;
void bfs(int s){
for(int i=1;i<=N;i++){
in[i]=0;
dis[cnt][i]=0x3f3f3f3f;
}
que.push(s);
dis[cnt][s]=0;
while(!que.empty()){
int tp=que.front();
que.pop();
if(in[tp])
continue;
in[tp]=1;
for(int i=0;i<G[tp].size();i++){
int v=G[tp][i];
if(dis[cnt][v]>dis[cnt][tp]+1){
dis[cnt][v]=dis[cnt][tp]+1;
que.push(v);
}
}
}
cnt++;
}
vector<pair<int,int> > hb;
int main(){
scan_d(N);
scan_d(M);
for(int i=0;i<=N;i++)
fa[i]=i;
int u,v;
int fx,fy;
for(int i=0;i<M;i++){
scan_d(u);
scan_d(v);
fx=find(u);
fy=find(v);
if(fx==fy){
hb.emplace_back(make_pair(u,v));
}
else{
fa[fx]=fy;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
}
lca_init();
for(int i=0;i<hb.size();i++){
G[hb[i].first].emplace_back(hb[i].second);
G[hb[i].second].emplace_back(hb[i].first);
}
for(int i=0;i<hb.size();i++)
bfs(hb[i].first);
int ans;
scan_d(Q);
while(Q--){
scan_d(u);
scan_d(v);
ans=dep[u]+dep[v]-2*dep[LCA(u,v)];
for(int i=0;i<cnt;i++)
ans=min(ans,dis[i][u]+dis[i][v]);
printf("%d\n",ans);
}
return 0;
}
| 
转播
