CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
题目链接
数据结构课上机碰到的题目，也太硬核了……
题面上的特别条件m-n<21是关键，要怎么用呢？
先随便选一个点作为根建一棵树，那么分以下两种情况来讨论：
- 若 s 到 t 的最短路径不经过非树边，直接求出 LCA 就可以轻松得出答案。
- 若 s 到 t 的最短路径经过非树边，就可以直接用非树边的端点作为 s 到 t 的中转点来更新答案。由于非树边最多有 21 条，这样的特殊点最多有 42 个，直接预处理出这 42 个点到其它点的最短路就可以了。
这里建树直接写了一个树剖，方便后面求 LCA。 稀疏图上 SPFA 快的一比……
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct Graph
{
struct Vertex
{
vector<int> o, i;
int siz, dep, top, dfn;
};
struct Edge : pair<int, int>
{
ll len;
Edge(int x, int y, ll z) : pair<int, int>(x, y), len(z) {}
};
vector<Vertex> v;
vector<Edge> e;
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
v[ed.first].o.push_back(e.size());
v[ed.second].i.push_back(e.size());
e.push_back(ed);
}
int ch(int u, int i = 0)
{
return e[v[u].o[i]].second;
}
int fa(int u, int i = 0)
{
return e[v[u].i[i]].first;
}
};
struct BellmanFord : Graph
{
BellmanFord(int n) : Graph(n) {}
void ask(int s, vector<ll> &d)
{
d.assign(v.size(), INF);
vector<int> flag(v.size(), d[s] = 0);
for (deque<int> q(flag[s] = 1, s); !q.empty(); q.pop_front())
for (int u = q.front(), i = flag[u] = 0, k, to; i < v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second,
d[to] > d[u] + e[k].len)
{
d[to] = d[u] + e[k].len;
if (!flag[to])
flag[to] = 1, q.push_back(to);
}
}
};
struct TreeDiagram : BellmanFord
{
TreeDiagram(const Graph &g, int root) : BellmanFord(g.v.size())
{
build(root, g);
int cnt = v[root].dfn = v[root].dep = 1;
dfs(v[root].top = root, cnt);
}
void build(int u, const Graph &g)
{
v[u].siz = 1;
for (int i = 0, k, to; i < g.v[u].o.size(); ++i)
if (k = g.v[u].o[i], to = g.e[k].second, !v[to].siz)
{
build(to, g);
v[u].siz += v[to].siz;
Graph::add(g.e[k]);
if (v[ch(u)].siz < v[to].siz)
swap(v[u].o.front(), v[u].o.back());
}
}
void dfs(int u, int &cnt)
{
for (int i = 0, to; i < v[u].o.size(); ++i)
{
v[to = ch(u, i)].dfn = ++cnt;
v[to].top = i ? to : v[u].top;
v[to].dep = v[u].dep + 1;
dfs(to, cnt);
}
}
int lca(int x, int y)
{
for (; v[x].top != v[y].top; x = fa(v[x].top))
if (v[v[x].top].dep < v[v[y].top].dep)
swap(x, y);
if (v[x].dep < v[y].dep)
swap(x, y);
return y;
}
};
int main()
{
int n, m;
scanf("%d%d", &n, &m);
BellmanFord g(n + 1);
for (int i = 0, x, y, z; i < m; ++i)
{
scanf("%d%d%d", &x, &y, &z);
g.add({x, y, z});
g.add({y, x, z});
}
TreeDiagram t(g, 1);
vector<ll> d[63];
for (int i = m = 0; i < n; ++i)
if (t.v[i].o.size() + t.v[i].i.size() < g.v[i].o.size())
g.ask(i, d[m++]);
t.ask(1, d[m]);
scanf("%d", &n);
for (int i = 0, x, y; i < n; ++i)
{
scanf("%d%d", &x, &y);
ll ans = d[m][x] + d[m][y] - 2 * d[m][t.lca(x, y)];
for (int j = 0; j < m; ++j)
ans = min(ans, d[j][x] + d[j][y]);
printf("%lld\n", ans);
}
}