AT_tkppc4_1_l.じゃんけん

我们有一个由 $N$ 个顶点和 $M$ 条边组成的图。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。每个顶点上标有一个字符，可能是 G、C 或 P。两个选手 anmichi 和 define 将在这个图上进行一场名为猜拳的游戏，规则如下：

猜拳规则

• 获胜：

  • 自己在 G 顶点，对方在 C 顶点。
  • 自己在 C 顶点，对方在 P 顶点。
  • 自己在 P 顶点，对方在 G 顶点。

• 失败：

  • 自己在 C 顶点，对方在 G 顶点。
  • 自己在 P 顶点，对方在 C 顶点。
  • 自己在 G 顶点，对方在 P 顶点。

• 平局：

  • 两人所在的顶点标有相同的字符。

初始时，anmichi 君位于顶点 $1$，define 君位于顶点 $N$，两人的初始得分都是 $0$ 分。游戏进行 $K$ 轮，过程如下：

1. 两人可以选择移动到相邻顶点或者保持不动，他们能移动到同一个顶点。
2. 根据猜拳结果加分：胜利得 $X$ 分，平局得 $Y$ 分，失败不得分。

define 君已经事先计划好第 $i\ (1 \leq i \leq K)$ 轮要去的顶点，也就是 $D_i$。anmichi 君了解对方的移动计划，目的是最大化自己的得分。请计算 anmichi 君在最佳策略下能获得的最高分。假设两人都知道每个顶点上标记的字符。

输入数据如下：

$N$ $M$ $K$ $X$ $Y$ $A_1$ $B_1$ $A_2$ $B_2$ $\ldots$ $A_M$ $B_M$ $C_1$ $C_2$ $\ldots$ $C_N$
$D_1$ $D_2$ $\ldots$ $D_K$

输出 anmichi 君可以获得的最大得分。

数据范围

• 每个输入都是整数。
• $2 \leq N \leq 2000$
• $1 \leq M \leq 5000$
• $1 \leq K \leq 2000$
• $1 \leq Y$
• $1 \leq A_i, B_i \leq N$
• $C_i$ 是 G、C、P。
• $1 \leq D_i \leq N$
• 初始时 $N = D_1$ 或者顶点 $N$ 与顶点 $D_1$ 之间连通。
• 对于 $1 \leq i \leq K-1$，$D_i = D_{i+1}$ 或者顶点 $D_i$ 与顶点 $D_{i+1}$ 之间连通。
• 图是简单图，不一定连通。

本翻译由 AI 自动生成