Mana Collection

题目描述

注意：本题时间限制为 5s，为默认值的 2.5 倍。内存限制为 512MB，为默认值的 2 倍。 Bessie 最近对魔法产生了兴趣，需要收集法力来施放一个非常重要的法术。Bessie 有 $N$（$1\le N\le 18$）个法力池，第 $i$ 个法力池每秒积累 $m_i$ 点法力（$1\le m_i\le 10^8$）。这些法力池通过 $M$（$0\le M\le N(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$）。当 Bessie 位于某个法力池时，她可以收集该位置储存的所有法力，并将其清空。时间 $0$ 时，所有法力池都是空的，且 Bessie 可以选择任意一个法力池作为起点。 回答 $Q$（$1\le Q\le 2\cdot 10^5$）个询问，每个询问由两个整数 $s$ 和 $e$（$1\le s\le 10^9$，$1\le e\le N$）指定。对于每个询问，若 Bessie 必须在第 $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$ 行，每行对应一个询问的答案。

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

提示

第一组样例解释：第一个询问：Bessie 在 5 秒后从 1 号池获得 5 点法力。 第二个询问：Bessie 在 5 秒后从 2 号池获得 50 点法力。 第三个询问：Bessie 在 100 秒后从 1 号池获得 100 点法力。 第四个询问：Bessie 在 90 秒后从 1 号池获得 90 点法力，并在 100 秒后从 2 号池获得 1000 点法力。

一个例子，其中 Bessie 能够收集到大得多的法力量。 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. Problem credits: Benjamin Qi

标签: USACO|2023|Platinum

来源

USACO|2023|Platinum