#P17827. [Ontak2022]HAP

[Ontak2022]HAP

题目描述

有 nn 座城市和 mm 条有向公路,每条公路具有正长度。保证从首都1可以到达每座城市。

公路总数仅比构成可达网络所必需的 n−1n-1 条多一点。给出 qq 次询问,每次询问从城市 ss 到城市 tt 的最短路长度。

输入格式

第一行三个整数 n,m,qn,m,q。

接下来 mm 行,每行三个整数 ai,bi,cia_i,b_i,c_i,表示一条从 aia_i 到 bib_i、长度为 cic_i 的公路。

接下来 qq 行,每行两个整数 sj,tjs_j,t_j,表示一次询问。

输出格式

对每次询问输出一行最短路长度;无法到达则输出 -1。

数据范围

1≤n,q≤5000001\le n,q\le500000;n−1≤m≤n+2000n-1\le m\le n+2000;1≤ai,bi,sj,tj≤n1\le a_i,b_i,s_j,t_j\le n;1≤ci≤10001\le c_i\le1000。原题未排除重边或自环。

子任务

子任务 附加限制 分值
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