← 返回题目
题库练习 村庄问路
← 上一题 下一题 →

A7139 | 村庄问路

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

题目描述

村庄里有 $n$ 座房子，并且有一些双向道路连接它们。每天人们总爱问这样的问题：

> “如果我想从房子 $A$ 去到房子 $B$，距离是多少？”

通常这个问题并不容易快速回答。但幸运的是，这个村庄的道路修建方式非常特殊：**任意两座房子之间都存在且仅存在一条简单路径**（简单路径指路径上不会重复经过同一个房子）。

你的任务是回答所有人的询问，即求出每次询问中从房子 $A$ 到房子 $B$ 的最短路长度（由于路径唯一，因此答案唯一）。

输入格式

第一行是一个整数 $T$（$T \le 10$），表示测试数据组数。

对于每组测试数据：

- 第一行包含两个整数 $n$ 和 $m$
其中 $2 \le n \le 40000$，$1 \le m \le 200$
分别表示房子的数量和询问的数量。

- 接下来 $n-1$ 行，每行包含三个整数 $i, j, k$，表示有一条长度为 $k$ 的双向道路连接房子 $i$ 和房子 $j$。
其中 $1 \le i,j \le n$，$0 < k \le 40000$。

- 接下来 $m$ 行，每行包含两个互不相同的整数 $i, j$，表示一次询问：求房子 $i$ 到房子 $j$ 的距离。

输出格式

对于每组测试数据，输出 $m$ 行，每行输出对应询问的答案。

**每组测试数据输出完毕后，额外输出一个空行。**

输入输出样例

输入 #1
2
3 2
1 2 10
3 1 15
1 2
2 3

2 2
1 2 100
1 2
2 1
输出 #1
10
25

100
100
C++ 编辑器
输入
输出