#P17789. Jellyfish and Inscryption

Jellyfish and Inscryption

题目描述

水母喜欢玩一个叫做“Inscryption”的游戏,这个游戏在一个有向无环图上进行,图中有 nn 个顶点和 mm 条边。所有的边 a→ba \to b 都满足 a<ba < b。

你需要沿着有向边从顶点 11 移动到顶点 nn,然后与最终 Boss 战斗。

在这个过程中,你会收集卡牌和道具。

每张卡牌有两个属性:生命值(HP)和伤害(damage)。如果一张卡牌的生命值为 aa,伤害为 bb,那么这张卡牌的能量为 a×ba \times b。

每个道具只有一个属性:能量值(power)。

除了顶点 11 和顶点 nn,有一些顶点会触发特殊事件。特殊事件包括:

  1. 你会获得一张生命值为 aa,伤害为 bb 的卡牌。
  2. 如果你至少有一张卡牌,选择你的一张卡牌并使其生命值增加 xx。
  3. 如果你至少有一张卡牌,选择你的一张卡牌并使其伤害增加 yy。
  4. 你会获得一个能量值为 ww 的道具。

当你到达顶点 nn 时,你可以选择至多一张你的卡牌,并将其伤害乘以 10910^9。

最终 Boss 非常强大,因此你希望最大化你所有卡牌和道具的能量之和。请你求出如果你最优地进行游戏,所有卡牌和道具的能量之和的最大值。

输入格式

第一行包含两个整数 nn 和 mm(2≤n≤2002 \leq n \leq 200,n−1≤m≤min⁡(n(n−1)2,2000)n-1 \leq m \leq \min(\frac{n(n-1)}{2}, 2000))——顶点数和边数。

接下来的 nn 行中,第 ii 行(1≤i≤n1 \leq i \leq n)描述了在顶点 ii 触发的特殊事件:

  • 0 —— 没有特殊事件。
  • 1 a b(1≤a,b≤2001 \leq a, b \leq 200)——你会获得一张生命值为 aa,伤害为 bb 的卡牌。
  • 2 x(1≤x≤2001 \leq x \leq 200)——如果你至少有一张卡牌,选择你的一张卡牌并使其生命值增加 xx。
  • 3 y(1≤y≤2001 \leq y \leq 200)——如果你至少有一张卡牌,选择你的一张卡牌并使其伤害增加 yy。
  • 4 w(1≤w≤1061 \leq w \leq 10^6)——你会获得一个能量值为 ww 的道具。

接下来的 mm 行,每行包含两个整数 uu 和 vv(1≤u<v≤n1 \leq u < v \leq n),表示一条从顶点 uu 到顶点 vv 的有向边。

保证每条边 (u,v)(u,v) 最多出现一次。

保证顶点 11 和顶点 nn 没有特殊事件。

保证对于所有 ii,存在一条从顶点 11 到顶点 nn 的路径经过顶点 ii。

输出格式

输出一个整数,表示你所有卡牌和道具的能量之和的最大值。

输入输出样例 #1

输入 #1

6 8
0
1 2 10
1 6 6
2 8
3 10
0
1 2
1 3
2 4
2 5
3 4
3 5
4 6
5 6

输出 #1

100000000000

输入输出样例 #2

输入 #2

4 3
0
4 1000000
4 1000000
0
1 2
2 3
3 4

输出 #2

2000000

输入输出样例 #3

输入 #3

16 15
0
1 1 10
1 10 1
2 4
3 4
1 20 20
2 30
3 20
1 1 100
2 9
1 1 200
2 9
3 10
1 190 100
2 10
0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16

输出 #3

20000000005600

输入输出样例 #4

输入 #4

9 9
0
1 1 200
3 200
3 200
3 200
3 200
1 200 200
3 200
0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
1 9

输出 #4

80000000001000

输入输出样例 #5

输入 #5

9 8
0
1 20 200
3 200
3 200
2 5
1 100 200
3 200
3 200
0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

输出 #5

60000000015000

输入输出样例 #6

输入 #6

16 34
0
0
0
2 6
3 1
4 27
4 40
3 9
0
2 6
1 8 1
0
2 2
1 10 7
2 9
0
2 4
3 10
2 11
2 7
13 15
3 15
2 3
6 14
4 12
10 12
9 10
7 8
4 13
11 12
4 6
11 16
14 15
2 5
5 15
9 13
8 14
1 3
2 15
12 16
7 10
4 5
1 2
4 11
4 9
4 16
3 6
6 8
7 11
15 16

输出 #6

133000000040

说明/提示

在第一个样例中,我们可以按如下顺序进行游戏:

  • 从顶点 11 移动到顶点 22,获得一张生命值为 22,伤害为 1010 的卡牌。
  • 从顶点 22 移动到顶点 44,选择在顶点 22 获得的卡牌,并使其生命值增加 88。
  • 从顶点 44 移动到顶点 66,选择在顶点 22 获得的卡牌,并将其伤害乘以 10910^9。

最终,我们会有一张生命值为 (2+8)=10(2+8)=10,伤害为 10×109=101010 \times 10^9=10^{10} 的卡牌,其能量为 10×1010=101110 \times 10^{10}=10^{11}。因为我们只有在顶点 22 获得的这张卡牌,所以所有卡牌和道具的能量之和为 101110^{11}。

由 ChatGPT 4.1 翻译