← 返回题目列表

Codeforces · 1187/G

G. 联合起来

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

某个非常秘密组织的领导人决定邀请所有其他成员参加会议。该组织的所有成员都居住在同一个城镇,该城镇可以表示为由 $$$m$$$ 双向街道连接的 $$$n$$$ 十字路口。会议将在十字路口附近的领导人家里举行$$$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$$$, ..., $$$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$$$后领导者的最小不满情绪。

示例

输入 #1

3 2 4 2 3
3 3 3 3
1 2
2 3

输出 #1

52

输入 #2

3 3 4 2 3
3 2 2 3
1 2
2 3
2 3

输出 #2

38

注意

第一次测试中的最佳操作方案如下:

- 第一人沿街道$$$2$$$到达十字路口$$$2$$$,然后沿街道$$$1$$$到达十字路口$$$1$$$并参加会议;
- 第二个人在十字路口$$$3$$$等待一分钟,然后沿街道$$$2$$$到达十字路口$$$2$$$,然后沿街道$$$1$$$到达十字路口$$$1$$$并参加会议;
- 第三人在十字路口$$$3$$$等待两分钟,然后沿街道$$$2$$$到达十字路口$$$2$$$,然后沿街道$$$1$$$到达十字路口$$$1$$$并参加会议;
- 第四个人在十字路口$$$3$$$等待三分钟,然后沿街道$$$2$$$到达十字路口$$$2$$$,然后沿街道$$$1$$$到达十字路口$$$1$$$并参加会议。