NC19814 最短路

题目地址：

https://ac.nowcoder.com/acm/problem/19814

基本思路：

题意很明了就是让我们每次在图中查询任意两点的最短路。
数据范围很大肯定不能使用 $floyd$ 算法，而且也不是树同样也不能使用 $lca$ 快速求树上距离，
但是题目保证了图联通，而且数据范围里 $1≤m≤n+100$ ，因此我们可以将这个联通图看做一棵树加上了一些边。
那么首先我们对图跑一个生成树，将这些多出来的边先放在一边，
单单对于树的部分，我们先用 $lca$ 求树上距离的方法计算出 $a,b$ 的树上距离;
然后我们将这些多出来的边加回来，然后对于每条边我们暴力找它的一个端点 $i$ 跑一遍单源最短路(边权为 $1$ 直接 $bfs$ )，
然后每次再用 $dis[i][a] + dis[i][b]$ 更新 $a$ , $b$ 的最小最短路就行了。
题目时限 $1s$ ,可能是我的 $lca$ 板子太丑了卡了很久常才在 $900ms$ 跑完QAQ。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(ll x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 1e5 + 110;
int n,m;
struct edge {
    int next, v;
}edges[maxn << 1];
int cnt;
int head[maxn],par[maxn],sz[maxn];
void init() {
  cnt = 0;
  for(int i = 0 ; i <= n ; i++) par[i] = i,head[i] = -1,sz[i] = 0;
}
void add_edge(int u,int v) {
  edges[cnt].next = head[u];
  edges[cnt].v = v;
  head[u] = cnt++;
}
/*    lca 求树上距离    */
int dep[maxn];
int f[maxn][21];
void dfs(int u,int fa) {
  dep[u] = dep[fa] + 1;
  for (register int i = 0; i <= 19; i++)
    f[u][i + 1] = f[f[u][i]][i];
  for (int i = head[u]; i != -1; i = edges[i].next) {
    int v = edges[i].v;
    if (v == fa)
      continue;
    f[v][0] = u;
    dfs(v, u);
  }
}
int lca(int x,int y) {
  if (dep[x] < dep[y])
    swap(x, y);
  for (register int i = 20; i >= 0; i--) {
    if (dep[f[x][i]] >= dep[y])
      x = f[x][i];
    if (x == y)
      return x;
  }
  for (register int i = 20; i >= 0; i--) {
    if (f[x][i] != f[y][i]) {
      x = f[x][i];
      y = f[y][i];
    }
  }
  return f[x][0];
}
int dist(int a,int b) {
  return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}
/*    size 优化并查集     */
int find(int x) {
  return par[x] == x ? x : par[x] = find(par[x]);
}
bool same(int x,int y){
  return find(x) == find(y);
}
void unite(int x,int y) {
  x = find(x), y = find(y);
  if (x == y) return;
  if (sz[x] < sz[y]) {
    par[x] = y;
    sz[y] += sz[x];
  } else {
    par[y] = x;
    sz[x] += y;
  }
}

/*    暴力处理多出来的边    */
vector<pii> vec;
int num = 0;
int dis[110][maxn];
bool vis[maxn];
void bfs(int s){
  queue<int> que; num++;
  for(int i = 0 ; i <= n ; i++) dis[num][i] = INF,vis[i] = false;
  dis[num][s] = 0;
  que.push(s);
  while (!que.empty()){
    int u = que.front();
    que.pop();
    if(vis[u]) continue;
    vis[u] = true;
    for(int i = head[u] ; i != -1 ; i = edges[i].next){
      int to = edges[i].v;
      if(dis[num][to] > dis[num][u] + 1) {
        dis[num][to] = dis[num][u] + 1;
        que.push(to);
      }
    }
  }
}
signed main() {
  n = read(), m = read();
  init();
  int u, v;
  rep(i, 1, m) {
    u = read(), v = read();
    /*    最小生成树    */
    if (same(u,v)) {
      vec.emplace_back(mp(u, v));
    } else {
      unite(u,v);
      add_edge(u, v);
      add_edge(v, u);
    }
  }
  dfs(1, 0);

  /*   将多出来的边加回去   */
  for (auto it : vec) {
    add_edge(it.first, it.second);
    add_edge(it.second, it.first);
  }

  bool use[maxn]; // 防止对重复的端点多次计算;
  num = 0;
  mset(use,false);
  for (auto it : vec) {
    if (!use[it.first]) use[it.first] = true, bfs(it.first);
  }

  int q, a, b,ans;
  q = read();
  while (q--) {
    a = read(), b = read();
    ans = dist(a, b); // 树上距离部分;
    // 用暴力部分更新答案;
    for (int i = 1; i <= num; i++) ans = min(ans, dis[i][a] + dis[i][b]);
    printf("%d\n",ans);
  }
  return 0;
}