#P17827. [Ontak2022]HAP
[Ontak2022]HAP
题目描述
有 座城市和 条有向公路,每条公路具有正长度。保证从首都1可以到达每座城市。
公路总数仅比构成可达网络所必需的 条多一点。给出 次询问,每次询问从城市 到城市 的最短路长度。
输入格式
第一行三个整数 。
接下来 行,每行三个整数 ,表示一条从 到 、长度为 的公路。
接下来 行,每行两个整数 ,表示一次询问。
输出格式
对每次询问输出一行最短路长度;无法到达则输出 -1。
数据范围
;;;。原题未排除重边或自环。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | m=n−1 | 21 |
| 2 | n,q≤2000,且所有 cᵢ=1 | 37 |
| 3 | n,q≤100000,m≤n+200,且所有 cᵢ=1 | 34 |
| 4 | 无额外限制 | 8 |
样例 1
输入:
8 9 4
1 4 1
3 1 1
5 6 1
6 3 1
2 4 1
4 7 1
6 2 1
1 5 1
6 8 1
1 4
5 1
3 7
8 2
输出:
1
3
3
-1