3873. [USACO23 Jan Platinum] Mana Collection

【题目描述】

贝西需要为一个非常重要的法术收集法力。贝西有 $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

【样例1输出】

5
50
100
1090

【样例1解释】

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

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

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

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

【样例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

【样例2输出】

160000000
239999988050000000
119992550000000

【数据规模与约定】

测试点 $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$：没有其他约束条件 。