5325. 最短路径 II（Shortest Paths II）
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 ## 输入格式 第一行包含三个整数 `n`, `m`, 和 `q`：分别表示城市数量、道路数量和查询数量。 接下来的 `m` 行描述道路，每行包含三个整数 `a`, `b`, 和 `c`：表示城市 `a` 和 `b` 之间存在一条长度为 `c` 的双向道路。 最后 `q` 行描述查询，每行包含两个整数 `a` 和 `b`：要求确定城市 `a` 和 `b` 之间的最短路径长度。 ## 输出格式 对于每个查询，输出对应的最短路径长度。如果两个城市之间不存在路径，则输出 `-1`。 ## 输入输出样例 ### 输入 #1 ``` 4 3 5 1 2 5 1 3 9 2 3 3 1 2 2 1 1 3 1 4 3 2 ``` ### 输出 #1 ``` 5 8 -1 3 ``` ## 说明/提示 ### 数据规模与约定 - 1 \le n \le 500 - 1 \le m \le n² - 1 \le q \le 10⁵ - 1 \le a, b \le n - 1 \le c \le 10⁹