题意:给出一张无向图,每次询问两点之间的最短路,满足$m - n <= 20$
$n, m, q \leqslant 10^5$
非常好的一道题。
首先建出一个dfs树。
因为边数-点数非常少,所以我们可以对于某些非树边特殊考虑。
具体做法是:对于非树边连接的两个点,暴力求出它们到所有点的最短路
对于询问的$(x, y)$
用树上的边,以及非树边连接的点到他们的最短路之和更新答案
由于边数的限制,非树边连接的点不会超过$2*(m - (n - 1)) = 42$个
#include<bits/stdc++.h>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define LL long long
using namespace std;
const int MAXN = 2 * 1e5 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M, Q, head[MAXN], num = 0, vis[MAXN], fa[MAXN][21], dep[MAXN], happen[MAXN];
LL dis[50][MAXN], Tdis[MAXN];
vector<int> p;
struct Edge {
LL u, v, w, f, nxt;
}E[MAXN];
inline void AddEdge(int x, int y, int z) {
E[num] = (Edge) {x, y, z, 0, head[x]};
head[x] = num++;
}
void dfs(int x, int _fa) {
vis[x] = 1; dep[x] = dep[_fa] + 1;
for(int i = head[x]; ~i; i = E[i].nxt) {
int to = E[i].v;
if(vis[to]) continue;
E[i].f = E[i ^ 1].f = 1;
Tdis[to] = Tdis[x] + (LL)E[i].w;
fa[to][0] = x;
dfs(to, x);
}
}
void Dij(int x, int id) {
memset(dis[id], 0x7f, sizeof(dis[id])); dis[id][x] = 0;
memset(vis, 0, sizeof(vis));
priority_queue<Pair> q; q.push(MP(0, x));
while(!q.empty()) {
int p = q.top().se; q.pop();
if(vis[p]) continue;
for(int i = head[p]; ~i; i = E[i].nxt) {
int to = E[i].v;
if(dis[id][to] > dis[id][p] + E[i].w && (!vis[to]))
dis[id][to] = dis[id][p] + E[i].w, q.push(MP(-dis[id][to], to));
}
}
}
void Pre() {
for(int j = 1; j <= 20; j++)
for(int i = 1; i <= N; i++)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int lca(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
for(int i = 20; i >= 0; i--)
if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
if(x == y) return x;
for(int i = 20; i >= 0; i--)
if(fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
main() {
// freopen("a.in", "r", stdin);
memset(head, -1, sizeof(head));
N = read(); M = read();
for(int i = 1; i <= M; i++) {
int x = read(), y = read(), z = read();
AddEdge(x, y, z);
AddEdge(y, x, z);
}
dfs(1, 0);
for(int i = 0; i < num; i++)
if(!E[i].f) {
if(!happen[E[i].u]) p.push_back(E[i].u), happen[E[i].u] = 1;
if(!happen[E[i].v]) p.push_back(E[i].v), happen[E[i].v] = 1;
}
for(int i = 0; i < p.size(); i++)
Dij(p[i], i);
Pre();
int Q = read();
while(Q--) {
int x = read(), y = read();
LL ans = Tdis[x] + Tdis[y] - 2 * Tdis[lca(x, y)];
for(int i = 0; i < p.size(); i++)
ans = min(ans, dis[i][x] + dis[i][y]);
cout << ans << endl;
}
return 0;
}