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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| #include <iostream>
#define maxn 100010
#define maxm 100010
#define Maxn 200010
#define Maxm 200010
#define ll long long
using namespace std;
int n, m, q;
struct Edge {
int to, next, w;
} e[maxm * 2], E[Maxm * 2]; int c1, head[maxn], c2, Head[Maxn];
inline void add_edge(int u, int v, int w) {
e[c1].to = v; e[c1].w = w;
e[c1].next = head[u]; head[u] = c1++;
}
inline void add_Edge(int u, int v, int w) {
E[c2].to = v; E[c2].w = w;
E[c2].next = Head[u]; Head[u] = c2++;
}
inline void Add_Edge(int u, int v, int w) {
add_Edge(u, v, w); add_Edge(v, u, w);
}
int dfn[maxn], fa[maxn], low[maxn], fr[maxn], cnt; ll pre[maxn], sum[Maxn];
void solve(int u, int v, int w) {
int t = v; pre[v] = sum[++cnt] = 0;
while (t != u) {
sum[cnt] += fr[t];
pre[fa[t]] = pre[t] + fr[t];
t = fa[t];
} sum[cnt] += w;
t = v;
while (t != u) {
Add_Edge(t, cnt, min(pre[t] + w, sum[cnt] - (pre[t] + w)));
t = fa[t];
} Add_Edge(u, cnt, 0);
}
void dfs(int u) {
static int cnt = 0;
dfn[u] = low[u] = ++cnt;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to, w = e[i].w; if (v == fa[u]) continue;
if (!dfn[v]) {
fa[v] = u; fr[v] = w;
dfs(v); low[u] = min(low[u], low[v]);
}
else low[u] = min(low[u], dfn[v]);
if (low[v] > dfn[u]) Add_Edge(u, v, w);
}
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to, w = e[i].w;
if (u == fa[v] || dfn[v] < dfn[u]) continue;
solve(u, v, w);
}
}
int dep[Maxn], f[Maxn][21]; ll dis[Maxn];
void dfs(int u, int fa) {
for (int i = Head[u]; ~i; i = E[i].next) {
int v = E[i].to, w = E[i].w; if (v == fa) continue;
dep[v] = dep[u] + 1; f[v][0] = u; dis[v] = dis[u] + w;
dfs(v, u);
}
}
void init_lca(int n) {
for (int j = 1; j <= 20; ++j)
for (int i = 1; i <= n; ++i) f[i][j] = f[f[i][j - 1]][j - 1];
}
int get_lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = 20; ~i; --i)
if (dep[f[x][i]] >= dep[y]) x = f[x][i];
if (x == y) return x;
for (int i = 20; ~i; --i)
if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
int jump(int x, int y) {
for (int i = 20; ~i; --i)
if (dep[f[x][i]] > dep[y]) x = f[x][i];
return x;
}
int main() { fill(head, head + maxn, -1); fill(Head, Head + Maxn, -1);
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> q; cnt = n;
for (int i = 1; i <= m; ++i) {
int x, y, z; cin >> x >> y >> z;
add_edge(x, y, z); add_edge(y, x, z);
} dfs(1); dfs(1, 0); init_lca(cnt);
for (int i = 1; i <= q; ++i) {
int x, y, l; cin >> x >> y; l = get_lca(x, y);
if (l <= n) cout << dis[x] + dis[y] - 2 * dis[l] << "\n";
else {
int u = jump(x, l), v = jump(y, l); ll ans = 0;
if (pre[u] > pre[v]) swap(u, v);
ans = dis[x] - dis[u] + dis[y] - dis[v] + min(pre[v] - pre[u], sum[l] - (pre[v] - pre[u]));
cout << ans << "\n";
}
}
return 0;
}
|