← 返回题目列表

Codeforces · 1051/F

F. 最短的陈述

中文机器翻译题面 查看原题

给您一个加权无向连通图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。

你应该回答 $$$q$$$ 查询,第 $$$i$$$ 查询是找到顶点 $$$u_i$$$ 和 $$$v_i$$$ 之间的最短距离。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m~(1 \le n, m \le 10^5, m - n \le 20)$$$ — 图中顶点和边的数量。

接下来的 $$$m$$$ 行包含边:第 $$$i$$$ 边是整数三元组 $$$v_i, u_i, d_i~(1 \le u_i, v_i \le n, 1 \le d_i \le 10^9, u_i \neq v_i)$$$。这个三元组意味着在权重为$$$d_i$$$的顶点$$$u_i$$$和$$$v_i$$$之间存在一条边。保证图不存在自环和重边。

下一行包含一个整数 $$$q~(1 \le q \le 10^5)$$$ — 查询数。

接下来的 $$$q$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i~(1 \le u_i, v_i \le n)$$$ — 查询的描述。

注意限制 $$$m - n ~ \le ~ 20$$$。

输出

打印 $$$q$$$ 行。

第 $$$i$$$ 行应包含第 $$$i$$$ 查询的答案 — 顶点 $$$u_i$$$ 和 $$$v_i$$$ 之间的最短距离。

示例

输入 #1

3 3
1 2 3
2 3 1
3 1 5
3
1 2
1 3
2 3

输出 #1

3
4
1

输入 #2

8 13
1 2 4
2 3 6
3 4 1
4 5 12
5 6 3
6 7 8
7 8 7
1 4 1
1 8 3
2 6 9
2 7 1
4 6 3
6 8 2
8
1 5
1 7
2 3
2 8
3 7
3 4
6 8
7 8

输出 #2

7
5
6
7
7
1
2
7