#P18900. [2026多校联测]旅行

[2026多校联测]旅行

题目背景

小 Z 非常热爱旅行,有一天他来到了一个陌生的城市,发现这里的出租车以一种奇怪的方式计价……

题目描述

小 Z 来到的城市 A 可以用 nn 个路口与 mm 条单向道路来描述,出租车只能沿着单向道路行驶。每个路口有一个过路费 aia_i,每条道路有一个通行时间 wiw_i。

出租车的计费方式如下:一次行驶从一个路口出发,到达另一个路口。对某次行驶,设经过的所有路口(包含起点与终点)的过路费最大值为 MM,经过的所有单向道路的通行时间之和为 SS,则这次行驶的费用为 M×SM\times S。注意一个路口与一条单向道路均可以被经过多次,并多次计入 MM 与 SS 之中。

小 Z 在城市 A 中规划了 qq 次旅行,每次旅行形如 (si,ti)(s_i,t_i),表示他希望从 sis_i 号路口乘坐出租车到达 tit_i 号路口。他想知道所需的最小费用是多少。特殊地,如果小 Z 无法从 sis_i 号路口出发到达 tit_i 号路口,则请输出 −1-1。

输入格式

第一行包含两个正整数 n,mn,m,表示路口的数量与单向道路的数量。

第二行包含 nn 个正整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示 nn 个路口的过路费。

接下来 mm 行,每行包含三个正整数 ui,vi,wiu_i,v_i,w_i,分别表示一条单向道路的起点、终点与通行时间。

接下来一行包含一个正整数 qq,表示小 Z 规划的旅行数量。

接下来 qq 行,每行包含两个正整数 si,tis_i,t_i,分别表示一次旅行的起点、终点。

输出格式

共输出 qq 行,每行包含一个整数,表示最小的费用,或输出 −1-1。

样例 1

8 14
1 2 3 4 5 6 7 8
1 2 9
2 3 3
4 1 2
2 4 7
4 5 6
3 8 10
6 3 5
8 7 9
7 4 1
1 7 3
5 2 4
6 8 1
5 8 7
3 5 9
6
5 7
1 4
3 4
6 7
8 6
2 8
112
28
100
80
-1
104

数据范围

对所有数据,保证 1≤n≤5001\le n\le500,0≤m≤n(n−1)0\le m\le n(n-1),1≤q≤1041\le q\le10^4,1≤ai,wi≤1061\le a_i,w_i\le10^6,si≠tis_i\ne t_i,保证图中不含重边与自环。

测试点编号 n≤n\le m≤m\le 特殊限制
1-6 1010 n(n−1)n(n-1) 无
7-8 500500 aia_i 均为 11
9-10 5050 200200 无
11-13 n(n−1)n(n-1)
14-16 500500 20002000
17-20 n(n−1)n(n-1)