Shortest Routes II

题目描述

有 n 个城市和它们之间的 m 条道路。你的任务是处理 q 个查询，每个查询需要你确定两座给定城市之间最短路线的长度。

输入格式

第一行输入包含三个整数 n、m 和 q：城市数、道路数和查询数。 接下来有 m 行描述道路。每行有三个整数 a、b 和 c：城市 a 与城市 b 之间有一条长度为 c 的道路。所有道路都是双向的。 最后有 q 行描述查询。每行有两个整数 a 和 b：确定城市 a 与城市 b 之间最短路线的长度。

输出格式

对每个查询打印最短路线的长度。如果不存在路线，则打印 -1。

4 3 5
1 2 5
1 3 9
2 3 3
1 2
2 1
1 3
1 4
3 2

5
5
8
-1
3

提示

$1 \le n \le 500$ $1 \le m \le n^2$ $1 \le q \le 10^5$ $1 \le a,b \le n$ $1 \le c \le 10^9$

标签: CSES1672|图论

来源

CSES1672|图论