[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 ### 样例输入 #1 ``` 2 1 1 10 1 2 10 4 5 1 5 2 100 1 100 2 ``` ### 样例输出 #1 ``` 5 50 100 1090 ``` ## 样例 #2 ### 样例输入 #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 ``` ## 提示 对于第一个样例： 第一次询问。贝西在 $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$：没有其他约束条件 。

**Note: The time limit for this problem is 5s, 2.5 times the default. The memory limit for this problem is 512MB, twice the default.** Bessie has recently taken an interest in magic and needs to collect mana for a very important spell. Bessie has $N(1 \le N \le 18)$ mana pools, the ith of which accumulates $m_i$ mana per second $(1 \le m_i \le 10^8)$. The pools are linked by a collection of $M (0 \le M \le N(N−1))$ directed edges $(a_i,b_i,t_i)$, meaning that she can travel from $a_i$ to $b_i$ in $t_i$ seconds $(1 \le a_i,b_i \le N, a_i \neq b_i, 1 \le t_i \le 10^9)$. Whenever Bessie is present at a pool, she can collect all the mana stored at that location, emptying it. At time $0$, all mana pools are empty, and Bessie can select any pool to start at. Answer $Q(1 \le Q \le 2 \cdot 10^5)$ queries, each specified by two integers $s$ and $e (1 \le s \le 10^9, 1 \le e \le N)$. For each query, determine the maximum amount of mana Bessie can collect in s seconds if she must be at mana pool $e$ at the end of the $s$-th second.

First line contains $N$ and $M$. Next line contains $m_1,m2, \cdots ,m_N$. Next $M$ lines contain $a_i,b_i,t_i$. No ordered pair $(a_i,b_i)$ appears more than once in the input. Next line contains $Q$. Next $Q$ lines contain two integers $s$ and $e$.

$Q$ lines, one for each query.

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

5
50
100
1090

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

### Explanation for Sample 1 First query: Bessie takes $5$ mana from pool $1$ after $5$ seconds. Second query: Bessie takes $50$ mana from pool $2$ after $5$ seconds. Third query: Bessie takes $100$ mana from pool $1$ after $100$ seconds. Fourth query: Bessie takes $90$ mana from pool $1$ after $90$ seconds and $1000$ mana from pool $2$ after $100$ seconds. ### Explanation for Sample 2 An example where Bessie is able to collect much larger amounts of mana. ### Scoring - Inputs $3-4$: $N \le 10$,$Q \le 100$ - Inputs $5-9$: $N \le 10$ - Inputs $10-14$: $Q \le 100$ - Inputs $15-17$: $N=16$ - Inputs $18-20$: $N=17$ - Inputs $21-24$: No additional constraints.