牛客国庆集训派对Day6 J 最短路

题目

解析

1. 从原图中扣出来一个树，然后求LCA的ST表
2. 对于多余的边，可以对于每个边上的点都跑一遍最短路，然后求经过这个点查询的u,v的最短路
   OK!

 // 以下是LCA模板 const int maxn = 2e5+100; const int maxlogv = 20; vector<int > G[maxn]; bool vis[maxn]; int id[maxn],dis[maxn]; int vs[maxn*2],depth[maxn*2]; int dp[maxn*2][maxlogv]; void dfs(int node,int fa,int d,int &k){ id[node] = k; vs[k] = node; depth[k++] = d; // dis[node] = distance; for(int i = 0;i < G[node].size(); ++i){ // Edge &t = G[node][i]; int v = G[node][i]; if(v == fa) continue; dis[v] = dis[node]+1; dfs(v,node,d+1,k); vs[k] = node; depth[k++] = d; } } void init_rmq(int n){ for(int i = 0;i < n ; ++i) dp[i][0] = i; for(int j = 1;(1<<j) <= n; ++j){ for(int i = 0;i + (1<<j)-1 < n; ++i){ if(depth[dp[i][j-1]]< depth[dp[i+(1<<(j-1))][j-1]]) dp[i][j] = dp[i][j-1]; else dp[i][j] = dp[i+(1<<(j-1))][j-1]; } } } int query(int l,int r){ int k = 0; while((1<<(k+1)) <= r-l+1) k++; if(depth[dp[l][k]] < depth[dp[r-(1<<k)+1][k]]) return dp[l][k]; else return dp[r-(1<<k)+1][k]; } int lca(int u,int v){ return vs[query(min(id[u],id[v]),max(id[u],id[v]))]; } void init(int n){ int k = 0; dfs(0,-1,0,k); init_rmq(2*n-1); } // 本题相关 vector<int > G1[maxn]; int d[maxn]; int ans[maxn]; int qu[maxn],qv[maxn]; int n,m,q; set<int> s; void dfs1(int u,int fa){ vis[u] = 1; for(int i = 0;i < G1[u].size(); ++i){ int v = G1[u][i]; if(v == fa) continue; if(vis[v]){ s.insert(v); s.insert(u); continue; } dfs1(v,u); G[u].Pb(v); } } void Bfs(int s){ memset(vis,0,sizeof(vis)); rep(i,0,n) d[i] = INF; queue<int> Q; Q.push(s); d[s] = 0; vis[s] = 1; while(!Q.empty()){ int u = Q.front(); Q.pop(); for(int i = 0,v;i <G1[u].size(); ++i){ v = G1[u][i]; if(vis[v]) continue; d[v] = d[u]+1; vis[v] = 1; Q.push(v); } } rep(i,0,q){ ans[i] = min(ans[i],d[qu[i]]+d[qv[i]]); } } int main(void){ scanf("%d%d",&n,&m); for(int i = 0;i < m; ++i){ int u,v; scanf("%d%d",&u,&v); u--,v--; G1[u].push_back(v); G1[v].push_back(u); } dfs1(0,-1); init(n); scanf("%d",&q); rep(i,0,q){ scanf("%d%d",&qu[i],&qv[i]); qu[i]--,qv[i]--; ans[i] = dis[qu[i]]+dis[qv[i]]-2*dis[lca(qu[i],qv[i])]; } for(auto c: s){ Bfs(c); } rep(i,0,q){ printf("%d\n",ans[i]); } return 0; } ``