← 返回题目列表

AtCoder · ttpc2022_j

J. 宝石游戏

中文机器翻译题面 查看原题

配点 : 400 点

問題文

N 頂点 M 给定了一个有向边的图。顶点标有 1 减去 N 号码位于侧面。 它的编号为 1 减去 M 的编号,边是指向 i (1 ≤ i ≤ M) 是顶点 A_i 到顶点 B_i 的边。该图可能存在自环,但没有重边。保证从任何顶点出发的边数至少为 1 条。
个顶点中有 K 个放置了宝石。i 番目 (1 ≤ i ≤ K号宝石位于顶点 V_i ,价值为 W_i 。

。使用这个图,First 君和 Second 君进行游戏。游戏开始时,First 君在顶点 F ,Second 君在顶点 S 。从 First 君开始,First 君和 Second 君交替执行以下操作:

  • 从自己当前所在的顶点出发的边 1 选择一条边,沿着它移动到下一个顶点。如果移动到的顶点上有宝石,就将其收集,同时该宝石将从图上移除。

当收集完所有宝石,或游戏中出现了与之前盘面完全相同的情况(轮次、每个玩家的位置、剩余宝石状态完全相同)时,游戏结束。

双方都将尽量行动,使(自己收集的宝石价值总和) - (对方收集的宝石价值总和)尽可能大,因此在游戏结束时求(First君收集宝石的价值总和) - (Second君收集宝石的价值总和)。

制約

  • 所有输入均为整数
  • 2 ≤ N ≤ 30
  • 1 ≤ F, S ≤ N
  • 1 ≤ A_i, B_i ≤ N (1 ≤ i ≤ M)
  • (A_i, B_i) ≠ (A_j, B_j) (1 ≤ i < j ≤ M)
  • 哪个 x (1 \le x \le N)也适用。 A_i = x 纳鲁 如果 i 存在
  • 1 ≤ K ≤ 10
  • 1 ≤ V_1 < \dots < V_K ≤ N
  • V_i \notin \{F, S\} (1 ≤ i ≤ K)
  • 1 ≤ W_i ≤ 10^8 (1 ≤ i ≤ K)

入力

输入是按以下格式从标准输入给出的。

N M F S
A_1 B_1
\vdots
A_M B_M
K
V_1 W_1
\vdots
V_K W_K

出力

打印答案。 来自


入力例 1

5 16 1 1
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 2
3 4
3 5
4 2
4 3
4 5
5 2
5 3
5 4
4
2 4
3 84
4 38
5 96

出力例 1

46

可以从任意顶点收集任何宝石。游戏按以下方式进行:

  • First君移动到顶点 1 到顶点 5 并获得价值为 96 的宝石。
  • Second君移动到顶点 1 到顶点 3 并获得价值为 84 的宝石。
  • First君移动到顶点 5 到顶点 4 并获得价值为 38 的宝石。
  • Second君移动到顶点 3 到顶点 2 并获得价值为 4 的宝石。

因此,答案是 (96 + 38) - (84 + 4) = 46 。


入力例 2

8 16 8 4
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1
1 5
2 6
3 7
4 8
5 1
6 2
7 3
8 4
6
1 29
2 34
3 41
5 7
6 26
7 94

出力例 2

-23

入力例 3

5 5 2 1
1 1
2 3
3 4
4 5
5 2
2
4 1000000
5 100000

出力例 3

1100000

入力例 4

10 20 1 2
1 4
1 7
2 2
2 4
3 6
3 3
4 8
4 7
5 7
5 1
6 9
6 2
7 9
7 3
8 8
8 6
9 7
9 8
10 10
10 2
8
3 92067840
4 2874502
5 36253165
6 70758738
7 4768969
8 16029185
9 16207515
10 44912151

出力例 4

132484345