A6161. 「USACO 2023.1 Platinum」Mana Collection
编程题
省选/NOI-
知识点
题目描述
**题目译自 [USACO 2023 January Contest, Platinum](http://usaco.org/index.php?page=jan23results) Problem 2. [Mana Collection](http://usaco.org/index.php?page=viewproblem2&cpid=1285)**
Bessie 最近对魔法产生了兴趣，并且为了一个非常重要的咒语收集法力。Bessie 有 $N$ 个法力池，第 $i$ 个池子每秒可以收集 $m_i$ 单位的法力。这些池子被一组 $M$ 条有向边 $(a_i,b_i,t_i)$ 相连，表示她可以在 $t_i$ 秒内从 $a_i$ 到 $b_i$。Bessie 无论何时出现在一个池子处，她都可以收集那个池子中所有的法力，也就是清空它。在时刻 $0$，所有的法力池都是空的，并且 Bessie 可以选择任意的法力池作为起点。
回答 $Q$ 个询问，每个询问用两个整数 $s$ 和 $e$ 表示。对于每个询问，确定如果 Bessie 在第 $s$ 秒结尾必须在池子 $e$ 处的情况下，她所能收集到的最多法力值是多少。
Bessie 最近对魔法产生了兴趣，并且为了一个非常重要的咒语收集法力。Bessie 有 $N$ 个法力池，第 $i$ 个池子每秒可以收集 $m_i$ 单位的法力。这些池子被一组 $M$ 条有向边 $(a_i,b_i,t_i)$ 相连，表示她可以在 $t_i$ 秒内从 $a_i$ 到 $b_i$。Bessie 无论何时出现在一个池子处，她都可以收集那个池子中所有的法力，也就是清空它。在时刻 $0$，所有的法力池都是空的，并且 Bessie 可以选择任意的法力池作为起点。
回答 $Q$ 个询问，每个询问用两个整数 $s$ 和 $e$ 表示。对于每个询问，确定如果 Bessie 在第 $s$ 秒结尾必须在池子 $e$ 处的情况下，她所能收集到的最多法力值是多少。
输入格式
第一行两个整数 $N\ (1\le N\le 18)$ 和 $M\ (0\le M\le N(N-1))$。
接下来一行为 $m_1,m_2,\ldots,m_N\ (1\le m_i\le 10^8)$。
接下来 $M$ 行，每行三个整数 $a_i,b_i,t_i\ (1\le a_i,b_i\le N,a_i\neq b_i,1\le t_i\le 10^9)$。输入中没有有序数对 $(a_i,b_i)$ 会出现超过一次。
接下来一行一个整数 $Q\ (1\le Q\le 2\cdot 10^5)$。
接下来 $Q$ 行，每行两个整数 $s\ (1\le s\le 10^9)$ 和 $e\ (1\le e\le N)$。
接下来一行为 $m_1,m_2,\ldots,m_N\ (1\le m_i\le 10^8)$。
接下来 $M$ 行，每行三个整数 $a_i,b_i,t_i\ (1\le a_i,b_i\le N,a_i\neq b_i,1\le t_i\le 10^9)$。输入中没有有序数对 $(a_i,b_i)$ 会出现超过一次。
接下来一行一个整数 $Q\ (1\le Q\le 2\cdot 10^5)$。
接下来 $Q$ 行，每行两个整数 $s\ (1\le s\le 10^9)$ 和 $e\ (1\le e\le N)$。
输出格式
输出 $Q$ 行，表示对询问的回答。
输入输出样例
输入 #1
2 1 1 10 1 2 10 4 5 1 5 2 100 1 100 2
输出 #1
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
输出 #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 组数据：无附加限制
- 5-9 组数据：$N\le 10$
- 10-14 组数据：$Q\le 100$
- 15-17 组数据：$N=16$
- 18-20 组数据：$N=17$
- 21-24 组数据：无附加限制