#P18505. Yet Another Shortest Path Query
Yet Another Shortest Path Query
Yet Another Shortest Path Query
在图论中,平面图是指可以画在平面上、使任意两条边仅能在公共端点处相交的图。具体的一种无交叉画法称为平面嵌入:把每个顶点映射到平面上的一个点,把每条边映射到连接其两个端点的平面曲线,各曲线除公共端点外互不相交。
给定一个有 个顶点、 条边的无向平面图,顶点编号为 。第 条边连接 ,长度为 。
接下来有 个询问。第 个询问给出两个顶点 ,请计算从 到 的、包含不超过三条边的最短路径长度;如果不存在这样的路径,则报告不存在。
输入格式
第一行包含两个整数 (,)。
接下来 行,第 行包含三个整数 (,,),描述一条无向边。保证任意一对顶点之间至多有一条边,且给定的图是平面图。输入不提供平面嵌入,也不保证图连通。
接下来一行包含一个整数 ()。
随后 行,第 行包含两个整数 (,)。
输出格式
对于每个询问输出一行整数,表示包含不超过三条边的最短路径长度。如果不存在这样的路径,则输出 -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