NC19814(最短路 )
感受
思路
复杂度分析
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100000 + 10; const int maxm = 200000 + 500; struct edge{ int v, nex; }e[maxm]; int head[maxn], cnt, n, m, fa[maxn]; void add_edge(int u, int v){ e[cnt] = (edge){v, head[u]}; head[u] = cnt++; } void init(){ cnt = 0; for(int i = 1; i <= n; i++){ head[i] = -1; fa[i] = i; } } int find_fa(int x){ return x == fa[x] ? x : fa[x] = find_fa(fa[x]); } void join(int x, int y){ x = find_fa(x); y = find_fa(y); if(x != y) fa[x] = y; } bool same(int x, int y){ return find_fa(x) == find_fa(y); } struct node{ int u, v; }res[200]; int tot; int ff[maxn][25], dep[maxn]; void dfs(int u, int f, int d){ dep[u] = d; ff[u][0] = f; for(int i = 1; i <= 17; i++){ ff[u][i] = ff[ff[u][i - 1]][i - 1]; } int v; for(int i = head[u]; ~i; i = e[i].nex){ v = e[i].v; if(v == f) continue; dfs(v, u, d + 1); } } int lca(int u, int v){ if(dep[u] < dep[v]) swap(u, v); for(int d = dep[u] - dep[v], i = 0; d; d >>= 1, i++){ if(d & 1) u = ff[u][i]; } if(u == v) return u; for(int i = 17; i >= 0; i--){ if(ff[u][i] != ff[v][i]){ u = ff[u][i]; v = ff[v][i]; } } return ff[u][0]; } node query[maxn]; int q; int ans[maxn], dis[maxn], vis1[maxn]; bool vis[maxn]; void bfs(int s){ for(int i = 1; i <= n; i++){ vis1[i] = false; } dis[s] = 0; queue<int> que; que.push(s); vis1[s] = true; while(!que.empty()){ int u = que.front(), v; que.pop(); for(int i = head[u]; ~i; i = e[i].nex){ v = e[i].v; if(vis1[v]) continue; que.push(v); vis1[v] = true; dis[v] = dis[u] + 1; } } for(int i = 1; i <= q; i++){ ans[i] = min(ans[i], dis[query[i].u] + dis[query[i].v]); } } int main(){ scanf("%d%d", &n, &m); init(); int u, v; for(int i = 1; i <= m; i++){ scanf("%d%d", &u, &v); if(same(u, v)){ res[++tot] = (node){u, v}; } else{ join(u, v); add_edge(u, v); add_edge(v, u); } } dfs(1, 0, 1); scanf("%d", &q); for(int i = 1; i <= q; i++){ scanf("%d%d", &u, &v); query[i] = (node){u, v}; ans[i] = dep[u] + dep[v] - 2 * dep[lca(u, v)]; } for(int i = 1; i <= tot; i++){ add_edge(res[i].u, res[i].v); add_edge(res[i].v, res[i].u); } for(int i = 1; i <= tot; i++){ u = res[i].u; v = res[i].v; if(!vis[u]){ bfs(u); vis[u] = true; } if(!vis[v]){ bfs(v); vis[v] = true; } } for(int i = 1; i <= q; i++){ printf("%d\n", ans[i]); } return 0; }