Codeforces 1051F(最短路+生成树+树图结合)

Codeforces 1051F
题意:给出一个边比点数多至多$20$条的无向连通图,每条边有一个边权,多次询问两点间最短路。
由于特殊条件,我们可以随便建一棵生成树(又称 DFS 树),然后就会只有最多$20$条边不在树中。
对于每个二元组询问$(u,v)$,我们答案有两种情况:
1、只走树上的边
2、必须经过一条树外的边
对于第一个很容易用 LCA 求出来。对于第二个,我们记录这条边的一个顶点$i$,然后用 dij 求出顶点的单源最短路,必走这条边的代价等价于$dis(i,u)+dis(i,v)$,因为这样的路径$(u,v)$就能覆盖这条边。两个情况取最小值即可。
知识点:
1、这种有特殊性题目可以将图转化为树,noip 货车运输是同样的思想,区别在于本题是随便一个生成树( DFS 树),而 noip 那题是要最小生成树
2、本题也一定程度上与 相同,最短路之后枚举边求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const LL MAXN = 100000 + 5, LOGS = 17, INF = 300000000000005ll;
struct edge {LL u, v, d;};
struct data {
LL u, d;
bool operator < (const data &b) const {return d > b.d;}
};
std::vector<edge > G[MAXN];
std::set<std::pair<LL, LL> > nt;
std::priority_queue<data > q;
LL n, m, Q, vis[MAXN], dep[MAXN], pre[MAXN][30], h[MAXN], dis[50][MAXN];
void dfs(LL u, LL fa) {
dep[u] = dep[fa] + 1, vis[u] = 1, pre[u][0] = fa;
for (LL i = 1; i <= LOGS; i++) pre[u][i] = pre[pre[u][i - 1]][i - 1];
for (LL i = 0; i < (LL)G[u].size(); i++) {
edge &e = G[u][i];
if (e.v != fa && !vis[e.v]) {
h[e.v] = h[u] + e.d;
dfs(e.v, u);
if (u < e.v) nt.erase(std::make_pair(u, e.v)); else nt.erase(std::make_pair(e.v, u));
}
}
}
void dij(LL st, LL d[MAXN]) {
for (LL i = 0; i <= n; i++) d[i] = INF, vis[i] = 0;
d[st] = 0, q.push((data){st, 0});
while (!q.empty()) {
data p = q.top(); q.pop();
if (vis[p.u]) continue; vis[p.u] = 1;
for (LL i = 0; i < (LL)G[p.u].size(); i++) {
edge &e = G[p.u][i];
if (d[e.v] > d[p.u] + e.d) d[e.v] = d[p.u] + e.d, q.push((data){e.v, d[e.v]});
}
}
}
LL LCA(LL a, LL b) {
if (dep[a] < dep[b]) std::swap(a, b);
for (LL i = LOGS; i >= 0; i--) if (dep[pre[a][i]] >= dep[b]) a = pre[a][i];
if (a == b) return a;
for (LL i = LOGS; i >= 0; i--) if (pre[a][i] != pre[b][i]) a = pre[a][i], b = pre[b][i];
return pre[a][0];
}
LL getdist(LL u, LL v) {return h[u] + h[v] - 2 * h[LCA(u, v)];}
void clean() {
ms(h, 0), ms(vis, 0), ms(dep, 0);
}
int solve() {
clean();
for (LL u, v, d, i = 1; i <= m; i++) {
scanf("%lld%lld%lld", &u, &v, &d);
G[u].push_back((edge){u, v, d}), G[v].push_back((edge){v, u, d});
if (u < v) nt.insert(std::make_pair(u, v)); else nt.insert(std::make_pair(v, u));
}
dfs(1, 0);
//for (LL i = 0; i < (LL)nt.size(); i++) printf("u=%lld v=%lld d=%lld\n", nt[i].u, nt[i].v, nt[i].d);
LL cnt = 0;
for (std::set<std::pair<LL, LL> >::iterator it = nt.begin(); it != nt.end(); it++) {
std::pair<LL, LL> e = *it;
LL &u = e.first, &v = e.second;
//printf("u=%lld v=%lld d=%lld\n", nt[i].u, nt[i].v, nt[i].d);
if (u > v) continue;
dij(u, dis[++cnt]);
}
//for (LL i = 1; i <= n; i++) for (LL j = 1; j <= n; j++) printf("i=%lld j=%lld lca=%lld\n", i, j, LCA(i, j));
scanf("%lld", &Q);
while (Q--) {
LL u, v; scanf("%lld%lld", &u, &v);
LL ans = getdist(u, v);
for (LL i = 1; i <= cnt; i++) {
ans = std::min(ans, dis[i][u] + dis[i][v]);
}
printf("%lld\n", ans);
}
return 0;
}
int main() {
scanf("%lld%lld", &n, &m), solve();
return 0;
}

------ 本文结束 ------