CSES1672 最短路径 II
#CS1672. 最短路径 II
最短路径 II
题目背景
翻译自 CSES-1672 题。
题目描述
有 n 个城市和 m 条航班连接它们。你的任务是处理 q 个查询，每个查询要求你确定两个给定城市之间的最短路径长度。
输入格式
第一行包含三个整数 n, m 和 q：分别表示城市的数量、道路的数量和查询的数量。
接下来有 m 行，每行描述一条道路。每行包含三个整数 a, b 和 c：表示城市 a 和城市 b 之间有一条道路，长度为 c。所有道路都是双向的。
然后有 q 行，每行描述一个查询。每行包含两个整数 a 和 b：你需要确定城市 a 和城市 b 之间的最短路径长度。
输出格式
对于每个查询，输出两城市之间的最短路径长度。如果没有路径，输出 −1−1−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
说明/提示