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
| #include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
using namespace std;
#define ll long long
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig = false, c = read(); !isdigit(c); c = read()) {
if (c == '-') iosig = true;
if (c == -1) return;
}
for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0');
if (iosig) x = -x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh = obuf;
inline void print(char c) {
if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
*ooh++ = c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) print('0');
else {
if (x < 0) print('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }
const int N = 10005;
int n, m, num=1, cnt, top, p, q, dep[N], stk[N], h[N], dfn[N], low[N], d[N<<1], siz[N<<1], dis[N<<1], e[N<<2], w[N<<2], pre[N<<2], f[15][N<<1];
vector<pair<int,int>> E[N<<1];
inline void add(int x, int y, int z){ e[++num]=y, w[num]=z, pre[num]=h[x], h[x]=num;}
void tarjan(int u, int fa=0){
dfn[u]=low[u]=++cnt;
stk[++top]=u;
for(int i=h[u]; i; i=pre[i]) if(i!=fa)
if(!dfn[e[i]]){
dep[e[i]]=dep[u]+w[i], tarjan(e[i], i^1);
low[u]=min(low[u], low[e[i]]);
if(dfn[e[i]]==low[e[i]])
f[0][e[i]]=u, E[u].push_back(make_pair(e[i], w[i]));
}
else if(dfn[e[i]]<dfn[u]){
low[u]=min(low[u], dfn[e[i]]);
siz[++n]=dep[u]-dep[e[i]]+w[i];
f[0][n]=e[i], E[e[i]].push_back(make_pair(n, 0));
for(int j=top, v; (v=stk[j])!=e[i]; --j)
f[0][v]=n, E[n].push_back(make_pair(v, dep[v]-dep[e[i]]));
}
--top;
}
void dfs(int u){
if(f[0][u]>p) dis[u]=min(dis[u], siz[f[0][u]]+dis[f[0][u]]*2-dis[u]);
for(auto i:E[u])
dis[i.first]=dis[u]+i.second, d[i.first]=d[u]+1, dfs(i.first);
}
inline int LCA(int x, int y, int &a, int &b){
if(d[x]<d[y]) swap(x, y);
int t=d[x]-d[y];
for(int i=14; ~i; --i) if(t>>i&1) x=f[i][x];
if(x==y) return x;
for(int i=14; ~i; --i) if(f[i][x]!=f[i][y]) x=f[i][x], y=f[i][y];
return a=x, b=y, f[0][x];
}
int main() {
read(n), read(m), read(q), p=n;
for(int i=1; i<=m; ++i){
static int x, y, z;
read(x), read(y), read(z);
add(x, y, z), add(y, x, z);
}
tarjan(1), dfs(1);
for(int i=1; i<=14; ++i) for(int j=1; j<=n; ++j) f[i][j]=f[i-1][f[i-1][j]];
while(q--){
static int x, y, lca, a, b;
read(x), read(y), lca=LCA(x, y, a, b);
if(lca<=p) print(dis[x]+dis[y]-dis[lca]*2);
else{
int tmp=abs(dep[a]-dep[b]);
print(dis[x]+dis[y]-dis[a]-dis[b]+min(tmp, siz[lca]-tmp));
}
print('\n');
}
return flush(), 0;
}
|