← 返回题目
题库练习 Shortest Statement
← 上一题 下一题 →

A6248 | Shortest Statement

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给你一个有 $n$ 个点，$m$ 条边的无向连通图。有 $q$ 次询问，第 $i$ 次询问回答从 $u_i$ 到 $v_i$ 的最短路的长度。

输入格式

第一行有两个数 $n$ 和 $m$（$1 \leq n,m \leq 10^5,m-n\leq 20$）。 接下来 $m$ 行包含一条边，输入三个正整数 $u_i,v_i,d_i(1 \leq u_i,v_i \leq n,1 \leq d_i \leq 10^9)$，意思是 $u_i$ 到 $v_i$ 之间有一条长度为 $d_i$ 的边。数据保证不存在自环和重边。下一行再输入一个数 $q$（$1 \leq q \leq 10^5$），接下来的 $q$ 行每行输入两个正整数 $u_i,v_i(1 \leq u_i,v_i \leq n)$。

输出格式

输出 $q$ 行，第 $i$ 行的输出的应为第 $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
C++ 编辑器
输入
输出