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
| #include <cstdio>
#include <vector>
#include <algorithm>
#define pb push_back
using namespace std;
template <class Type>
void read (Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
c == '-' && (flag = true);
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 1) + (x << 3) + c - '0';
flag && (x = ~x + 1);
}
template <class Type, class ...rest>
void read (Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
x < 0 && (putchar('-'), x = ~x + 1);
x > 9 && (write(x / 10), 0);
putchar('0' + x % 10);
}
const int N = 2e4 + 10, M = 16;
int top, stk[N];
int n, m, q, tot, d[N], s[N], r[N], sz[N], l[N], f[N][M];
struct Edge { int v, w; };
vector <Edge> g[N], e[N];
int stmp, dfn[N], low[N];
void tarjan (int u, int fa)
{
stk[++top] = u;
low[u] = dfn[u] = ++stmp;
for (Edge i : g[u])
if (!dfn[i.v])
{
l[i.v] = i.w;
r[i.v] = r[u] + i.w;
tarjan(i.v, u);
low[u] = min(low[u], low[i.v]);
if (low[i.v] >= dfn[u])
{
sz[++tot] = l[stk[top]] + r[stk[top]] - r[u];
int x;
do
{
x = stk[top--];
int t = r[x] - r[u]; t = min(t, sz[tot] - t);
e[tot].pb((Edge){x, t}), e[x].pb((Edge){tot, t});
} while (x ^ i.v);
e[tot].pb((Edge){u, 0}), e[u].pb((Edge){tot, 0});
}
}
else if (dfn[i.v] < dfn[u] && i.v ^ fa)
l[u] = i.w, low[u] = min(low[u], dfn[i.v]);
}
void dfs (int u)
{
for (Edge i : e[u]) if (i.v ^ f[u][0])
{
d[i.v] = d[u] + 1;
s[i.v] = s[u] + i.w;
f[i.v][0] = u;
for (int k = 0; k + 1 < M; ++k)
f[i.v][k + 1] = f[f[i.v][k]][k];
dfs(i.v);
}
}
int calc (int a, int b)
{
int x = a, y = b;
if (d[a] < d[b]) swap(a, b), swap(x, y);
for (int i = M - 1; ~i; --i)
if (f[a][i] && d[f[a][i]] >= d[b]) a = f[a][i];
if (a == b) return s[x] - s[y];
for (int i = M - 1; ~i; --i)
if (f[a][i] ^ f[b][i]) a = f[a][i], b = f[b][i];
if (f[a][0] <= n) return s[x] + s[y] - 2 * s[f[a][0]];
int t = abs(r[a] - r[b]); t = min(t, sz[f[a][0]] - t);
return s[x] - s[a] + s[y] - s[b] + t;
}
int main ()
{
read(n, m, q);
for (int a, b, c; m; --m)
{
read(a, b, c);
g[a].pb((Edge){b, c});
g[b].pb((Edge){a, c});
}
tot = n; tarjan(1, 0), --top; dfs(1);
for (int a, b; q; --q, puts(""))
read(a, b), write(calc(a, b));
return 0;
}
|