#P18900. [2026多校联测]旅行
[2026多校联测]旅行
题目背景
小 Z 非常热爱旅行,有一天他来到了一个陌生的城市,发现这里的出租车以一种奇怪的方式计价……
题目描述
小 Z 来到的城市 A 可以用 个路口与 条单向道路来描述,出租车只能沿着单向道路行驶。每个路口有一个过路费 ,每条道路有一个通行时间 。
出租车的计费方式如下:一次行驶从一个路口出发,到达另一个路口。对某次行驶,设经过的所有路口(包含起点与终点)的过路费最大值为 ,经过的所有单向道路的通行时间之和为 ,则这次行驶的费用为 。注意一个路口与一条单向道路均可以被经过多次,并多次计入 与 之中。
小 Z 在城市 A 中规划了 次旅行,每次旅行形如 ,表示他希望从 号路口乘坐出租车到达 号路口。他想知道所需的最小费用是多少。特殊地,如果小 Z 无法从 号路口出发到达 号路口,则请输出 。
输入格式
第一行包含两个正整数 ,表示路口的数量与单向道路的数量。
第二行包含 个正整数 ,表示 个路口的过路费。
接下来 行,每行包含三个正整数 ,分别表示一条单向道路的起点、终点与通行时间。
接下来一行包含一个正整数 ,表示小 Z 规划的旅行数量。
接下来 行,每行包含两个正整数 ,分别表示一次旅行的起点、终点。
输出格式
共输出 行,每行包含一个整数,表示最小的费用,或输出 。
样例 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-6 | 无 | ||
| 7-8 | 均为 | ||
| 9-10 | 无 | ||
| 11-13 | |||
| 14-16 | |||
| 17-20 |