来源：牛客网：
@[toc]
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 1048576K，其他语言2097152K 64bit IO Format: %lld
题目描述
给一个连通图，每次询问两点间最短路。每条边的长度都是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
题解：
我看了别人的讲解才逐渐明白。。我太菜了
题目是最短路，题目内容也是最短路，但是解法却不是常用的spfa等，因为询问的个数有点多（1 ~ 100000）
我们仔细看数据范围，m<n+100,什么意思？想想m = n-1时是一棵树，那我们就可以把他当做树处理，然后剩下的边再慢慢干
如果当做一棵树的话，边长为1，求最短路径，我们就可以通过最近公共祖先（lca）得到两点的最近距离，dep[a]+dep[b] - 2dep [ lca(a, b) ] (a的深度+b的深度，然后a和b有重复的部分，减去重复的部分)
然后我们看看多出来的100个边，会对结果有什么影响？
蓝色是原本的树，橙色，绿色是多出来的边
如果是橙色，对结果没有影响，如果是绿色会有影响
那么该如何处理？
我们可以把剩下多出来的边跑单元最短路（以这些边的一个端点开始）并记录下来
然后与原路径进行比较
a到b的最小距离就在dep[a] +dep[b]-2dep[ lca(a,b) ]与dis[a[i]]+dis[b[i]]中取最小值
不知道有没有听明白，我拿样例做个分析：
我们看一下样例，
1 2 2 3 1 4 4 3 2 4
多余的边是：1-2 , 4-3,
ans最开始的值就是树上的lca
ans={1,2,1,3}
然后开始跑1-2这个边，从1这个点开始，计算出1到个点的距离
dis={0,1,2,1}
然后更新最短距离：
ans[i] = min(ans[i], dis[a[i]] + dis[b[i]]);
a和b分别表示询问中a和b的距离
a[2]=1,b[2]=2
dis[a[2]]+dis[b[2]]=0+1=1<ans[2]
所以ans[2]=1
大致就是这个过程
代码：
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e9+7;
//const int mod = 998244353;
const double eps = 1e-10;
const double pi = acos(-1.0);
const int maxn = 1e6+10;
const ll inf = 0x3f3f3f3f;
const int dir[][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int n, m, depth[maxn], f[maxn][50];
int from[maxn], to[maxn << 1], nxt[maxn << 1], cnt = 1, Log[maxn], From[maxn];
bool vis[maxn], used[maxn];
//链式前向星加边
void addEdge (int u, int v) {
From[++cnt] = u, to[cnt] = v, nxt[cnt] = from[u], from[u] = cnt;
}
//计算深度&计算祖先
void dfs (int u, int fa) {
depth[u] = depth[fa] + 1;
vis[u] = 1;
for (register int i = 1; i <= Log[n]; ++i) {
if ((1 << i) > depth[u]) break;
f[u][i] = f[f[u][i - 1]][i - 1];
}
for (register int i = from[u]; i; i = nxt[i]) {
ll v = to[i];
if (vis[v]) continue;
used[i] = used[i ^ 1] = 1;
f[v][0] = u;
dfs (v, u);
}
}
//计算LCA
inline int LCA (int x, int y) {
if (depth[x] < depth[y]) swap(x, y);
//我们默认x为更深的那个点
for(register int i = Log[n] ; i >= 0 ; --i)
if(depth[x] - (1 << i) >= depth[y]) x = f[x][i];
//将x跳到和y同一深度上
if (x == y) return x;
for (register int i = Log[n]; i >= 0; --i)
if (f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
//一起向上跳
return f[x][0];
//不难看出，此时两个点均在其LCA的下方，往上跳一次即可
}
void init(){
Log[0] = -1;
for (register int i = 1, u, v; i <= m; ++i) {
cin >> u >> v;
addEdge (u, v); addEdge(v, u);
Log[i] = Log[i >> 1] + 1;
}
Log[n] = Log[n >> 1] + 1;
dfs(1, 0);
}
int dist(int p , int q){return depth[p] + depth[q] - 2 * depth[LCA(p , q)];}
int ans[maxn],a[maxn],b[maxn],dis[maxn], Q, q[maxn], h, t;
void bfs(int s){
for (int i = 1; i <= n; i++)dis[i] = inf;
dis[s] = 0;
h = t = 0;
q[++h] = s;
while (t < h) {
int u = q[++t];
for (int i = from[u]; i; i = nxt[i]){
int v = to[i];
if (dis[v] > dis[u] + 1)
dis[v] = dis[u] + 1, q[++h] = v;
}
}
for (int i = 1; i <= Q; i++)
ans[i] = min(ans[i], dis[a[i]] + dis[b[i]]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cin >> n >> m;
init();
cin >> Q;
for (int i = 1; i <= Q; i++){
cin >> a[i] >> b[i];
ans[i] = dist(a[i], b[i]);
}
int num = 0;
for (int i = 2; i <= cnt; i++)
if(!used[i]) {
used[i] = used[i ^ 1] = 1;
bfs(From[i]);
num++;
if(num > 101) break;
}
for (int i = 1; i <= Q; i++)
cout << ans[i] << endl;
return 0;
}
京公网安备 11010502036488号