CF1187G Gang Up

某个极为神秘的组织的首领决定邀请所有其他成员参加一次会议。该组织的所有成员都住在同一个小镇上，这个小镇可以表示为 $n$ 个路口，通过 $m$ 条双向街道连接。会议将在首领的家中举行，首领的家靠近路口 $1$。有 $k$ 名成员被邀请参加会议，第 $i$ 位成员住在路口 $a_i$ 附近。 所有成员会在同一时刻收到会议通知，并开始前往会议地点。每分钟的开始时，每个人都位于某个路口。他或她可以选择在当前路口等待一分钟，或者花一分钟沿着某条街道从当前路口走到另一个路口（显然，只有当街道的一端是当前路口时，才能开始沿该街道行走）。在第一分钟的开始时，每个人都在自己居住的路口。一旦某人到达路口 $1$，他或她会立即进入首领的家并参加会议。 显然，首领希望所有成员尽早到达。但由于组织极为神秘，首领又不希望引起太多关注。我们将首领的不满度定义如下： - 初始时不满度为 $0$； - 每当有一人到达路口 $1$ 时，不满度增加 $c \cdot x$，其中 $c$ 是某个固定常数，$x$ 是该人到达路口 $1$ 所花费的分钟数； - 每当有 $x$ 名成员在同一时刻、同一方向上沿同一条街道行走时，不满度增加 $dx^2$，其中 $d$ 是某个固定常数。这个惩罚不会叠加：例如，如果有两个人在同一时刻、同一方向上沿同一条街道行走，则增加 $4d$，而不是 $5d$。 在发送会议通知前，首领可以为每位成员指定他们应选择的路径和等待的地点。请帮助首领为每位成员制定计划，使他们都能到达路口 $1$，并且总不满度最小。

输入的第一行包含五个整数 $n$、$m$、$k$、$c$ 和 $d$（$2 \le n \le 50$，$n-1 \le m \le 50$，$1 \le k, c, d \le 50$），分别表示路口数、街道数、被邀请的成员数，以及影响不满度的两个常数。 第二行包含 $k$ 个整数 $a_1, a_2, \ldots, a_k$（$2 \le a_i \le n$），表示每位成员居住的路口编号。 接下来 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$，$x_i \ne y_i$），表示一条连接路口 $x_i$ 和 $y_i$ 的双向街道。可能有多条街道连接同一对路口。 保证任意两个路口之间都可以通过这些街道互相到达。

输出一个整数，表示所有成员到达路口 $1$ 后，首领的不满度的最小值。

对于第一个测试样例，最佳方案如下： - 第一位成员沿街道 $2$ 到达路口 $2$，然后沿街道 $1$ 到达路口 $1$ 并参加会议； - 第二位成员在路口 $3$ 等待一分钟，然后沿街道 $2$ 到达路口 $2$，再沿街道 $1$ 到达路口 $1$ 并参加会议； - 第三位成员在路口 $3$ 等待两分钟，然后沿街道 $2$ 到达路口 $2$，再沿街道 $1$ 到达路口 $1$ 并参加会议； - 第四位成员在路口 $3$ 等待三分钟，然后沿街道 $2$ 到达路口 $2$，再沿街道 $1$ 到达路口 $1$ 并参加会议。 由 ChatGPT 4.1 翻译