P9020 [USACO23JAN] Mana Collection P

题目描述

题目背景

注意：这个问题的时间限制是5秒，是默认的2.5倍。这个问题的内存限制是512MB，是默认值的两倍。

贝西需要为一个非常重要的法术收集法力。贝西有 $N$ $(1\le N\le 18)$ 个法力池，其中第 $i$ 个法力池每秒可积累 $m_i$ 法力 $(1\le m_i\le 10^8)$ 。这些池子由 $M$ $(0\le M\le N \cdot (N-1))$ 条有向边 $(a_i,b_i,t_i)$ 连接，这意味着她可以在 $t_i$ 秒内从 $a_i$ 移动到 $b_i$ $(1\le a_i, b_i\le N$, $a_i\neq b_i$, $1\le t_i\le 10^9)$ 。每当贝西出现在一个池子里，她就可以收集储存在那个地方的所有法力，把它清空。在 $0$ 的时候，所有的法力池都是空的，贝西可以选择任何一个池子来开始收集。

回答 $Q$ $(1\le Q\le 2\cdot 10^5)$ 个查询，每个查询由两个整数 $s$ 和 $e$ 指定 $(1\le s\le 10^9$，$1\le e\le N)$ 。对于每个查询，如果贝西在第 $s$ 秒结束时必须在法力池 $e$ 处，请确定她在 $s$ 秒内能收集的最大法力值。

输入格式

第一行包含 $N$ 和 $M$ 。

下一行包含 $m_1,m_2,\dots, m_N$ 。

接下来的 $M$ 行每行包含 $a_i,b_i,t_i$ 。在输入中没有一对有序的 $(a_i,b_i)$ 出现超过一次。

下一行包含 $Q$ 。

接下来的 $Q$ 行每行包含两个整数 $s$ 和 $e$ 。

输出格式

输出 $Q$ 行，每个查询所对应的答案。

输入输出样例 1

2 1
1 10
1 2 10
4
5 1
5 2
100 1
100 2

5
50
100
1090

输入输出样例 2

4 8
50000000 100000000 20000000 70000000
1 2 20
2 1 50
2 3 90
1 3 40
3 1 10
4 1 25
1 4 5
4 3 70
3
8 3
1000000000 1
500000 4

160000000
239999988050000000
119992550000000

说明/提示

对于第一个样例：

第一次询问。贝西在 $5$ 秒后从水池 $1$ 中取出 $5$ 个法力值。

第二次查询。 $5$ 秒后，贝西从水池 $2$ 中获取 $50$ 点法力。

第三次查询。 $100$ 秒后，贝西从水池 $1$ 中获取 $100$ 法力值。

第四次查询。 $90$ 秒后贝西从水池 $1$ 中获得 $90$ 法力， $100$ 秒后从水池 $2$ 中获得 $1000$ 法力。

测试点 $3-4$: $N\le 10, Q\le 100$ 。

测试点 $5-9$: $N\le 10$ 。

测试点 $10-14$: $Q\le 100$ 。

测试点 $15-17$: $N = 16$ 。

测试点 $18-20$: $N = 17$ 。

测试点 $21-24$：没有其他约束条件 。