#P18644. Jewel Game

Jewel Game

Jewel Game

题目描述

给定一张有 NN 个顶点、MM 条边的有向图。顶点编号为 1,…,N1,\ldots,N,边编号为 1,…,M1,\ldots,M。第 ii 条边从顶点 UiU_i 指向顶点 ViV_i。图中可能有自环,但没有重边;保证每个顶点至少有一条出边。

图中的一些顶点上共放有 KK 颗珠宝。第 ii 颗珠宝位于顶点 XiX_i,价值为 WiW_i。

Alice 和 Bob 在这张图上进行游戏。初始时,Alice 位于顶点 AA,Bob 位于顶点 BB。两人从 Alice 开始交替执行以下操作:

选择一条从自己当前所在顶点出发的边,沿着这条边移动到它指向的顶点。如果到达的顶点上有珠宝,则取得这颗珠宝,并将它从图上移除。

两枚棋子可以位于同一个顶点,彼此不阻挡移动。初始位置 AA 与 BB 也可以相同。

满足以下任意条件时,游戏结束:

  • 所有珠宝都已被取得。
  • 当前游戏状态曾经出现过。这里的状态由当前轮到谁行动、两名玩家各自的位置、剩余的珠宝集合共同确定。

游戏结束时,分数定义为:

(Alice 取得的珠宝价值之和)−(Bob 取得的珠宝价值之和)。(\text{Alice 取得的珠宝价值之和})-(\text{Bob 取得的珠宝价值之和})。

Alice 希望分数尽可能大,Bob 希望分数尽可能小。求双方都采用最优策略时的最终分数。

输入格式

N M A B
U_1 V_1
...
U_M V_M
K
X_1 W_1
...
X_K W_K

输入仅包含一组数据,所有数均为整数。

输出格式

输出一个整数,表示双方最优行动时的最终分数。

数据范围

  • 2≤N≤302\le N\le30。
  • 1≤A,B≤N1\le A,B\le N。
  • 1≤Ui,Vi≤N1\le U_i,V_i\le N。
  • 对任意 1≤i<j≤M1\le i<j\le M,(Ui,Vi)≠(Uj,Vj)(U_i,V_i)\ne(U_j,V_j)。
  • 对每个顶点 xx,至少存在一条边满足 Ui=xU_i=x。
  • 1≤K≤101\le K\le10。
  • 1≤X1<X2<⋯<XK≤N1\le X_1<X_2<\cdots<X_K\le N。
  • 对每个 ii,Xi∉{A,B}X_i\notin\{A,B\}。
  • 1≤Wi≤1081\le W_i\le10^8。

每点出度至少1且无重边,因此 N≤M≤N2N\le M\le N^2。

样例输入 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

样例输入 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