#P18505. Yet Another Shortest Path Query

Yet Another Shortest Path Query

Yet Another Shortest Path Query

在图论中,平面图是指可以画在平面上、使任意两条边仅能在公共端点处相交的图。具体的一种无交叉画法称为平面嵌入:把每个顶点映射到平面上的一个点,把每条边映射到连接其两个端点的平面曲线,各曲线除公共端点外互不相交。

给定一个有 nn 个顶点、mm 条边的无向平面图,顶点编号为 1,2,…,n1,2,\ldots,n。第 ii 条边连接 ui,viu_i,v_i,长度为 wiw_i。

接下来有 qq 个询问。第 ii 个询问给出两个顶点 si,tis_i,t_i,请计算从 sis_i 到 tit_i 的、包含不超过三条边的最短路径长度;如果不存在这样的路径,则报告不存在。

输入格式

第一行包含两个整数 n,mn,m(2≤n≤1062\le n\le10^6,1≤m≤1061\le m\le10^6)。

接下来 mm 行,第 ii 行包含三个整数 ui,vi,wiu_i,v_i,w_i(1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i,1≤wi≤1081\le w_i\le10^8),描述一条无向边。保证任意一对顶点之间至多有一条边,且给定的图是平面图。输入不提供平面嵌入,也不保证图连通。

接下来一行包含一个整数 qq(1≤q≤1061\le q\le10^6)。

随后 qq 行,第 ii 行包含两个整数 si,tis_i,t_i(1≤si,ti≤n1\le s_i,t_i\le n,si≠tis_i\ne t_i)。

输出格式

对于每个询问输出一行整数,表示包含不超过三条边的最短路径长度。如果不存在这样的路径,则输出 -1。

原样例 1

6 9
1 2 4
2 3 6
3 6 5
6 5 3
5 4 2
4 1 3
3 4 9
1 3 100
5 3 1
5
1 3
1 6
3 4
3 5
2 5
6
8
3
1
7

原样例 2

6 4
1 2 1
2 3 1
3 4 1
4 5 1
3
1 4
1 5
1 6
3
-1
-1