最短路计数问题

树形 dp 统计条数

Sightseeing

不妨设起点为ss,终点为tt,首先用dijkstra(s)\text{dijkstra}(s) 求出单源最短路
得到 uV: d(u)\forall \ u \in V: \ d(u)

先不考虑 “比最短路长度多11” 这种情况,f(v)f(v) 表示svs \to v 最短路可选方案数
对于边(u,v)(u, v),显然有转移
if d(v)=d(u)+e(u,v): f(v)+=f(u)\textbf{if} \ d(v) = d(u) + e(u, v): \ f(v) += f(u)
初始化f(s)=1, us: f(u)=0f(s) = 1, \ \forall u \neq s: \ f(u) = 0

如果顺着某条路径从ss 到达vv,路线长度恰好比最短路多11,那么有
sus \to u 沿最短路走,接着d(u)+e(u,v)=d(v)+1d(u) + e(u, v) = d(v) + 1,然后vtv \to t 继续沿着最短路走
对于节点uu,考虑v,e(u,v)\forall v, e(u, v),如果d(u)+e(u,v)=d(v)+1d(u) + e(u, v) = d(v) + 1
f(u)f(u)vvsvs \to v 长度恰好比最短路多11” 的答案有贡献

不妨用f(0,u)f(0, u) 表示uusus \to u 最短路径上的方案数
f(1,u)f(1, u) 表示sus \to u 的距离恰好为最短路径多11 的方案数,边(u,v)(u, v) 存在转移

  • 如果d(v)=d(u)+e(u,v)d(v) = d(u) + e(u, v),那么f(0,v)+=f(0,u), f(1,v)+=f(1,u)f(0, v) += f(0, u), \ f(1, v) += f(1, u)
  • 如果d(v)+1=d(u)+e(u,v)d(v) + 1 = d(u) + e(u, v),那么f(1,v)+=f(0,u)f(1, v) += f(0, u)

初始化u:f(0,u)=f(1,u)=0,f(0,s)=1\forall u: f(0,u) = f(1, u) = 0, \quad f(0, s) = 1
最后答案为f(0,t)+f(1,t)f(0, t) + f(1, t)

具体来说
dijkstra(s)\text{dijkstra}(s) 求出单源最短路u:d[u]\forall u: d[u],接下来对所有节点uu
根据d[u]d[u] 从小到大排序,对于每个节点uu,执行如上dp\text{dp}

容易弄错的地方是,由于存在f(0,u)f(1,v)f(0, u) \to f(1, v) 的转移
所以dp\text{dp} 枚举节点的时候,需要把u,f(0,u)\forall u, f(0, u) 先算出来,再算f(1,u)f(1, u)

最短路组合计数

社交网络
Cs,t(v)C_{s, t}(v) 表示经过vv 的从sts \to t 的最短路数目,可以考虑用 floyd 算法求解

先执行 floyd 算法,求出任意两点之间的最短路径u,v:f(u,v)\forall u, v: f(u, v)
下面来考虑任意两点间最短路数目C(u,v)C(u, v) 如何求解,先将任意两点的C(u,v)C(u, v) 初始化为11
对于 floyd 方程中满足f(u,v)=f(u,k)+f(k,v)f(u, v) = f(u, k) + f(k, v),令C(u,v)+=C(u,k)C(k,v)C(u, v) += C(u, k) \cdot C(k, v)
如果f(u,v)>f(u,k)+f(k,v)f(u, v) > f(u, k) + f(k, v),则令C(u,v)C(u,k)C(k,v)C(u, v) \leftarrow C(u, k) \cdot C(k, v)

Cs,t(k)C_{s, t}(k) 求解就比较简单,当发现满足f(s,t)=f(s,k)+f(k,t)f(s, t) = f(s, k) + f(k, t) 时,对于点kk
可以直接统计,I(k)+=Cs,t(k)C(s,t)\displaystyle I(k) += \frac{C_{s, t}(k)}{C(s, t)},实际上
Cs,t(k)=C(s,k)C(k,t)C_{s, t}(k) = C(s, k) \cdot C(k, t)

建新图统计

有时候图论的统计问题,预处理执行完最短路算法后,可以根据d(u)d(u) 信息
重新建图,新图往往是一个DAG\text{DAG},可以执行DAG\text{DAG} 上的dp\text{dp}

林中漫步

很容易想到满足从公司到家的路径,一定是一条最短路,问题就是最短路可能不止一条,执行单源最短路算法后
可以得到任意节点的距离信息u, d(u)\forall u, \ d(u)
满足条件的道路ABA \to B,实际上要求d(B)<d(A)d(B) < d(A),可以设计出如下算法

原图起点ss,终点tt,先反着执行dijkstra(t)\text{dijkstra}(t),得到d(u)d(u)
tst \to s 反着来执行DAG\text{DAG} 上的dp\text{dp},不妨用f(u)f(u) 表示从uu 出发的路径方案
边界为f(s)=1f(s) = 1

具体来说,枚举每一条边e(u,v)e(u, v)建立新图,当且仅当d(u)>d(v)d(u) > d(v) 时加入有向边(u,v)(u, v)
然后执行dp(t)dp(t),统计的时候,for vson(u): f(u)+=dp(v)\textbf{for} \ \forall v \in son(u): \ f(u) += dp(v)
dp(t)dp(t) 就是答案

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
typedef pair<int, int> PII;

const int maxn = 1000 + 10, inf = 0x3f3f3f3f;
const int maxm = 200000 + 10;
int n, m;
vector<PII> edges(maxm, PII(0, 0));

namespace Graph {
int n1 = 1, n2 = 1;
int h1[maxn], ver1[maxm], e1[maxm], ne1[maxm];
int h2[maxn], ver2[maxm], e2[maxm], ne2[maxm];

void initG() {
n1 = n2 = 1;
memset(h1, 0, sizeof h1);
memset(h2, 0, sizeof h2);
fill(edges.begin(), edges.end(), PII(0, 0));
}

void add1(int a, int b, int c) {
ver1[++n1] = b, e1[n1] = c, ne1[n1] = h1[a], h1[a] = n1;
edges[n1] = PII(a, b);
}
void add2(int a, int b, int c) {
ver2[++n2] = b, e2[n2] = c, ne2[n2] = h2[a], h2[a] = n2;
}
}

vector<int> d(maxn, inf);
int vis[maxn];

void dijkstra(int s) {
using namespace Graph;

priority_queue<PII, vector<PII>, greater<PII> > q;
fill(d.begin(), d.end(), inf);
memset(vis, 0, sizeof vis);
d[s] = 0, q.push(PII(0, s));

while (q.size()) {
auto x = q.top().second; q.pop();
if (vis[x]) continue;
vis[x] = 1;

for (int i = h1[x]; i; i = ne1[i]) {
int y = ver1[i];
if (d[y] > d[x] + e1[i]) {
d[y] = d[x] + e1[i];
q.push(PII(d[y], y));
}
}
}
}

void build() {
using namespace Graph;
for (int i = 2; i <= n1; i++) {
int u = edges[i].first, v = edges[i].second, w = e1[i];
//debug(d[u]);
if (d[u] > d[v]) add2(v, u, w);
}
}

ll f[maxn];
ll dp(int x) {
using namespace Graph;

if (f[x]) return f[x];
for (int i = h2[x]; i; i = ne2[i]) {
int y = ver2[i];
//debug(y);
f[x] += dp(y);
}
return f[x];
}

void init() {
memset(f, 0, sizeof f);
f[1] = 1;
}

int main() {
freopen("input.txt", "r", stdin);
using namespace Graph;

while (scanf("%d%d", &n, &m) == 2 && n) {
//init();
initG();

// get data
while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add1(a, b, c), add1(b, a, c);
}

dijkstra(2);

// build and dp
build();

init();
ll res = dp(2);
printf("%lld\n", res);
}
}

最短路建模

如何把一些问题抽象成最短路来解决,这也是算法中关注的焦点
最短路建模常用的技巧比如拆点,在实际开发过程中非常常用

Dijkstra 模版

机场快线
本例可作为 dijkstra 模板题

本例中起点ss,终点tt 都是确定的,很容易想到用单源最短路径解决
由于商业线只可以坐一站,可以枚举在哪一站开始坐商业线,不妨设在aa 站开始换乘商业线
我们需要最小化min\minf(s,a)+T(a,b)+f(b,t)f(s, a) + T(a, b) + f(b, t) 的值,其中T(a,b)T(a, b) 表示商业线aba \to b 耗费的时间

很显然f(s,a)f(s, a) 必然是经济线中sas \to a 的最短路径,f(b,t)f(b, t) 也是btb \to t 的最短路径
由于道路双向的,可以考虑预处理dijkstra\text{dijkstra},分别求出对于任意节点uu
ss 出发的单源最短路f(u)f(u),和从tt 出发的最短路g(u)g(u),这样只需要枚举中转站aa
求出minf(a)+T(a,b)+g(b)\min f(a) + T(a, b) + g(b) 即可

值得注意的是,很可能不需要用到商业线车票,在输出方案的时候
只在f(t)>f(a)+T(a,b)+g(b)f(t) > f(a) + T(a, b) + g(b) 的时候,更新中转点resares \leftarrow a

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
const int maxn = 1000 + 10, maxm = 2000 + 10;
const int inf = 0x3f3f3f3f;
int n, s, t, m, k, T[maxn][maxn];

namespace Graph {
int idx = 1;
int head[maxn], ver[maxm], ne[maxm], e[maxm];

void initG() {
idx = 1;
memset(head, 0, sizeof head);
}

void add(int a, int b, int c) {
ver[++idx] = b, e[idx] = c, ne[idx] = head[a], head[a] = idx;
}
}

int vis[maxn];
typedef pair<int, int> PII;
void dijkstra(int s, vector<int> &f, vector<int> &p) {
using namespace Graph;
fill(p.begin(), p.end(), 0);
fill(f.begin(), f.end(), inf);
memset(vis, 0, sizeof vis);

f[s] = 0;
priority_queue<PII, vector<PII>, greater<PII> > q;
q.push(PII(0, s));

while (q.size()) {
auto x = q.top().second; q.pop();
if (vis[x]) continue;
vis[x] = 1;

for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (f[y] > f[x] + e[i]) {
f[y] = f[x] + e[i], p[y] = x;
q.push(PII(f[y], y));
}
}
}
}

vector<int> f(maxn, inf), g(maxn, inf), pf(maxn, 0), pg(maxn, 0);
vector<PII> vec;

void dfs(const int u, const vector<int> &p, vector<int> &path) {
if (u == 0) return;

dfs(p[u], p, path);
path.push_back(u);
}

void solve() {
PII res(-1, -1);
dijkstra(s, f, pf), dijkstra(t, g, pg);

int ans = f[t];
for (auto x : vec) {
int u = x.first, v = x.second;

for (int kase = 0; kase < 2; kase++) {
if (ans > f[u] + T[u][v] + g[v]) {
ans = f[u] + T[u][v] + g[v];
res = PII(u, v);
}
swap(u, v);
}
}

// get path
if (res.first == -1) {
vector<int> path;
dfs(t, pf, path);
int fl = 0;
for (auto x : path) {
printf("%d", x);
++fl == (int)path.size() ? printf("\n") : printf(" ");
}
}
else {
vector<int> path1, path2;
int u = res.first, v = res.second;
dfs(u, pf, path1), dfs(v, pg, path2);
reverse(path2.begin(), path2.end());

vector<int> path;
for (auto x : path1) path.push_back(x);
for (auto x : path2) path.push_back(x);

int fl = 0;
for (auto x : path) {
printf("%d", x);
++fl == path.size() ? printf("\n") : printf(" ");
}
}

if (res.first == -1) puts("Ticket Not Used");
else printf("%d\n", res.first);
printf("%d\n", ans);
}

void init() {
memset(T, 0, sizeof T);
vec.clear();
}

int main() {
freopen("input.txt", "r", stdin);
using namespace Graph;

int cas = 0;
while (scanf("%d%d%d", &n, &s, &t) == 3) {
init();
initG();
if (cas++ != 0) puts("");

// build
scanf("%d", &m);
while (m--) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z), add(y, x, z);
}

scanf("%d", &k);
while (k--) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
vec.push_back(PII(x, y));
T[x][y] = T[y][x] = z;
}

// dijkstra
solve();
}
}

最短路树与删边最短路

Codeforces 1163F Indecisive Taxi Fee

给定一个nn 个点mm 条双向边的无向图GG,第ii 条道路通行费用为wiw_i
经过e1,e2,,eke_1, e_2, \cdots, e_k 的总花费为i=1kwek\sum_{i = 1}^{k} w_{e_k}

下面有qq 个问询,每个问询为(tj,xj)(t_j, x_j),把编号为tjt_j 的边的权值更改为xjx_j
对于每个问询,回答从1n1 \to n 的最小花费

最短路删边问题,可以考虑用最短路树,先来看最短路树的一个性质
CF1163F

很容易想到先求出原来的最短路树LL

  • 对于每个问询,如果修改的边ei(u,v)e_i(u, v) 不是最短路树上的边,不妨设旧边权为wiw_i,修改后的边权为xix_i
    对于任意点uu,在原图上从ss 开始跑一遍最短路记为f(u)f(u)
    再从tt 开始跑一遍最短路记为g(u)g(u)
    则修改后的最短路径为min{f(t), f(u)+g(v)+xi, f(v)+g(u)+xi}\min\{f(t), \ f(u) + g(v) + x_i, \ f(v) + g(u) + x_i\}
  • 如果ei(u,v)e_i(u, v) 是最短路树上的边,并且xi<wix_i < w_i,修改后的权值比原来权值更小
    最短路仍然是LL,求解的结果为f(t)wi+xif(t) - w_i + x_i

具体到编程实现上,最短路树可以用dijkstra\text{dijkstra} 求出(p(u),u)(p(u), u)
对于编号为ii 的边,需要知道edges(i)=(u,v)\text{edges}(i) = (u, v),并且inTree(u,v)\text{inTree}(u, v) 标记这条边是不是树边
这样以上情况都可以解决

下面来讨论ei(u,v)e_i(u, v) 代价增大的情况,当xi>wix_i > w_i 时候,最短路树可能就不是LL
可以推出一个结论,新的最短路树LL'LL 有着相同的前缀和后缀,可以为空

不妨设LL 中的节点为{s,u1,u2,uk,t}\{s, u_1, u_2, \cdots u_k, t\},如果LL'LL 没有公共前缀
LL' 路径为s[p1,p2,pk][ul,ul+1,]s \to [p_1, p_2, \cdots p_k] \to [u_{l}, u_{l+1}, \cdots]
而在dijkstra\text{dijkstra} 中求出f(ul)f(u_l),从suls \to u_{l} 的最短路径为
su1u2uls \to u_1 \to u_2 \to \cdots \to u_l,这条路径一定不会比其他路径更差,这与假设矛盾

根据这个结论,我们需要快速计算出不经过L[l,r]L[l, r] 的最短路,称为非树边最短路
实际上在dijkstra\text{dijkstra} 的时候,对于每一条非树边(u,v)(u, v),需要快速求出le(u),ri(v)\text{le}(u), \text{ri}(v)
uu 往左能够连到最短路树上le(u)\text{le}(u) 的点,ri(v)\text{ri}(v) 同理
那么非树边最短路不经过原最短路树[le(u),ri(v)1][\text{le}(u), \text{ri}(v)-1] 这一段(左开右闭)
此时非树边最短路径为z=f(u)+w(u,v)+g(v)z = f(u) + w(u, v) + g(v)
这个值对不经过原最短路树上[le(u),ri](v)1][\text{le}(u), \text{ri}](v)-1] 这一段,所形成的最短路径有贡献

这启发我们用线段树维护minv\text{minv},即不经过最短路上[li,ri][li, ri] 区间,所形成的最短路径
首先将最短路树上的点离散化,uID(u)u \to \text{ID}(u)
对每一个非树边(u,v)(u, v),执行区间修改change(le(u),ri(v)1,z)\text{change}(\text{le}(u), \text{ri}(v)-1, z)
这样处理问询e(u,v)e(u, v) 的时候,就是线段树的标准查询,query(ID(u))\text{query}(\text{ID}(u)) 即可
实际上我们要问询不经过e(u,v)e(u, v) 的最短路,由于左开右闭建线段树,所以问询不经过ID(u)\text{ID}(u) 的最短路

最后就是编程实现,如何快速求出le(u),ri(v)\text{le}(u), \text{ri}(v)
由于非树边最短路LL'LL 有公共前缀,先dijkstra\text{dijkstra} 求出最短路树,并标记点是否在树上
对于最短路树上的点uu,显然le(u)=ri(u)=ID(u)\text{le}(u) = \text{ri}(u) = \text{ID}(u)
再从ss 开始再执行dijkstra\text{dijkstra},执行松弛f(y)min(f(x)+w(x,y))f(y) \leftarrow \min(f(x) + w(x, y)) 的时候
如果yy 不在最短路树上,那么yy 可以连接到xx,执行le(y)le(x)\text{le}(y) \leftarrow le(x)
对称地从tt 开始再来一次dijkstra\text{dijkstra} 求出ri(u)ri(u)

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
typedef pair<int, int> PII;
typedef pair<ll, int> PLL;
const int maxn = 4e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m, q;

namespace Graph {
int idx = 1;
int ver[maxn], e[maxn], ne[maxn], id[maxn], h[maxn];

void initG() {
idx = 1;
memset(h, 0, sizeof h);
}

void add(int a, int b, int c, int i) {
ver[++idx] = b, e[idx] = c, id[idx] = i, ne[idx] = h[a], h[a] = idx;
}
}

namespace segTree {
struct node {
bool fl;
ll minv;
node() {
fl = 0, minv = inf;
}
};
vector<node> t(maxn<<2, node());

inline void push(int p) {
if (t[p].fl) {
t[p].fl = 0, t[p<<1].fl = 1, t[p<<1|1].fl = 1;
chmin(t[p<<1].minv, t[p].minv);
chmin(t[p<<1|1].minv, t[p].minv);
}
}

void change(int p, int l, int r, const int li, const int ri, ll val) {
if (li <= l && r <= ri) {
t[p].fl = 1, chmin(t[p].minv, val);
return;
}

push(p);
int mid = (l + r) >> 1;
if (li <= mid) change(p<<1, l, mid, li, ri, val);
if (ri > mid) change(p<<1|1, mid+1, r, li, ri, val);
//pull(p);
}

ll query(int p, int l, int r, int cur) {
if (l == r) {
return t[p].minv;
}
push(p);
int mid = (l + r) >> 1;
if (cur <= mid) return query(p<<1, l, mid, cur);
else return query(p<<1|1, mid+1, r, cur);
}
}

using namespace Graph;
using namespace segTree;
PII edges[maxn];
int w[maxn];

vector<ll> f[2];
vector<PII> p[2];
int vis[maxn];

vector<int> line;
int onPath[maxn], inTree[maxn];

int cnt = 0;
vector<int> le(maxn, 0), ri(maxn, 0);
map<int, int> mp;

void build() {
cnt = 0, mp.clear();
for (auto x : line) mp[x] = ++cnt;
for (auto x : line) le[x] = ri[x] = mp[x];
}

void dijkstra(int s, vector<ll> &f, vector<PII> &p, int fl = 0) {
priority_queue<PLL, vector<PLL>, greater<PLL> > q;
fill(f.begin(), f.end(), inf), fill(p.begin(), p.end(), PII(0, 0));
memset(vis, 0, sizeof vis);

f[s] = 0;
q.push(PLL(f[s], s));

while (q.size()) {
auto x = q.top().second; q.pop();
if (vis[x]) continue;
vis[x] = 1;

for (int i = h[x]; i; i = ne[i]) {
int y = ver[i];
if (f[y] > f[x] + e[i]) {
f[y] = f[x] + e[i], p[y] = PII(x, id[i]);

if (fl == 1 && !onPath[y]) le[y] = le[x];
else if (fl == 2 && !onPath[y]) ri[y] = ri[x];
q.push(PLL(f[y], y));
}
}
}
}

void get_path(int u, const vector<PII> &p, vector<int> &path) {
if (!u) return;
get_path(p[u].first, p, path);
path.push_back(u);
if (p[u].second) inTree[p[u].second] = 1;
}


void prework() {
dijkstra(1, f[0], p[0]);
get_path(n, p[0], line);

for (int i = 0; i < line.size()-1; i++) {
int u = line[i], v = line[i+1];
onPath[u] = onPath[v] = 1;
}
}

void upd() {
for (int i = 1; i <= m; i++) {
if (inTree[i]) continue;
int u = edges[i].first, v = edges[i].second;
ll z = f[0][u] + w[i] + f[1][v];
//debug(z);
if (le[u] <= ri[v]-1) change(1, 1, cnt-1, le[u], ri[v]-1, z);

swap(u, v);
z = f[0][u] + w[i] + f[1][v];
if (le[u] <= ri[v]-1) change(1, 1, cnt-1, le[u], ri[v]-1, z);
}
}

void init() {
for (int i = 0; i < 2; i++) {
f[i].resize(maxn), p[i].resize(maxn);
fill(f[i].begin(), f[i].end(), inf), fill(p[i].begin(), p[i].end(), PII(0, 0));
}

line.clear();
memset(onPath, 0, sizeof onPath);
memset(inTree, 0, sizeof inTree);
}

int main() {
freopen("input.txt", "r", stdin);
cin >> n >> m >> q;
initG(), init();

// graph
for (int i = 1; i <= m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c, i), add(b, a, c, i);
edges[i] = PII(a, b), w[i] = c;
}

prework(), build();
dijkstra(1, f[0], p[0], 1), dijkstra(n, f[1], p[1], 2);

upd();

// query
while (q--) {
int id, x;
scanf("%d%d", &id, &x);

if (!inTree[id]) {
ll res = f[0][n];
int u = edges[id].first, v = edges[id].second;
chmin(res, f[0][u] + x + f[1][v]);
chmin(res, f[1][u] + x + f[0][v]);
printf("%lld\n", res);
}
else {
int u = edges[id].first, v = edges[id].second;
if (w[id] > x) {
ll res = f[0][u] + x + f[1][v];
chmin(res, f[0][v] + x + f[1][u]);
printf("%lld\n", res);
continue;
}
ll res = f[0][n] - w[id] + x;
chmin(res, f[0][u] + x + f[1][v]);
chmin(res, f[1][u] + x + f[0][v]);
//debug(res);
int cur = min(mp[u], mp[v]);

chmin(res, query(1, 1, cnt-1, cur));
printf("%lld\n", res);
}
}
}