分数: 6 点
警告
2020 年 11 月 8 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
有 N 城镇编号 1 通过 N,和 M 道路。的 i第条路连接城镇 A_i 和镇 B_i 双向,你得到 C_i 当你经过那条路时的疲劳点。 对于每一对城镇来说,至多有一条道路直接连接这些城镇,并且可以通过穿过一些道路来在这些城镇之间行驶。 此外,每个城镇都有 A 型、B 型或 C 型传送器。传送器的位置由字符串指定 S;镇上的传送器 i 属于类型 S_i。 某些类型的传送器可能在任何城镇中都不存在。 您可以使用不同类型的传送器在两个城镇之间进行传送。当你这样做时,你会感到以下几点疲劳: 使用 A 型和 B 型传送器在城镇之间传送时的
- X_{\mathrm{AB}} 点; 使用 A 型和 C 型传送器在城镇之间传送时的
- X_{\mathrm{AC}} 点; 使用 B 型和 C 型传送器在城镇之间传送时的
- X_{\mathrm{BC}} 点。
你无法在具有相同类型传送器的城镇之间进行传送。 求从城镇出发时可能获得的最低疲劳总分 1 到镇 N 仅使用道路和传送器。
约束
- 2 \le N \le 10^5
- 1 \le M \le 10^5
- 1 \le X_{\mathrm{AB}}, X_{\mathrm{AC}}, X_{\mathrm{BC}} \le 10^9
- S 是一个长度为的字符串 N 组成
A,B,和C. - 1 \le A_i \le N
- 1 \le B_i \le N
- A_i \neq B_i
- 1 \le C_i \le 10^9
- 对于每对城镇,最多有一条道路直接连接这些城镇。
- 对于每对城镇,可以通过穿过一些道路在这些城镇之间行驶。
- 输入中的所有值,除了 S是整数。
输入
输入由标准输入按以下格式给出:
N M
X_{\mathrm{AB}} X_{\mathrm{AC}} X_{\mathrm{BC}}
S
A_1 B_1 C_1
A_2 B_2 C_2
A_3 B_3 C_3
\hspace{25pt} \vdots
A_M B_M C_M
输出
找出从城镇出发时获得的最小可能的疲劳总分 1 到镇 N.
示例输入 1
3 2 10 10 10 ABA 1 2 15 2 3 5
示例输出 1
15
如果你首先从城镇传送 1 (A 型)到城镇 2 (类型 B),然后使用 2- 从城镇出发的第 2 条路 2 到镇 3,你得到 10 + 5 = 15 疲劳点,这是最佳的。 请注意,两个城镇 1 和镇 3 有一个A型传送器,所以你不能直接在它们之间传送。
示例输入 2
3 2 10 1000000000 10 ABC 1 2 1000000000 2 3 1000000000
示例输出 2
20
如果你首先从城镇传送 1 (A 型)到城镇 2 (B 型)和来自城镇 2 (B 型)到城镇 C (类型C),你会得到 10 + 10 = 20 疲劳点,这是最佳的。 请注意,您可以从城镇传送 这次直接 1 到镇 3 ,但这不是最佳选择,因为从 A 类型的传送器传送到 C 类型的传送器需要花费成本 X_{\mathrm{AC}} = 1000000000 疲劳点。
示例输入 3
5 6 5 10 15 ABCBC 5 4 4 3 5 2 1 3 7 3 4 1 4 2 1 2 3 3
示例输出 3
8