J - ワープ Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

1 から N までの番号がついた N 個の町があります。 M 本の道路があり、i 番目の道路は町 A_i と町 B_i を双方向に結んでいて、通ると C_i の疲労度がたまります。
どの 2 つの町も、その間を直接結んでいる道路は多くとも 1 つで、どの 2 つの町もいくつかの道路を辿って行き来できます。
また、それぞれの町にはタイプ A, タイプ B, タイプ C のいずれかのワープ台があります。ワープ台の配置は文字列 S によって与えられ、町 i のワープ台のタイプは S_i です。どの町にも存在しないワープ台のタイプがあるかもしれません。
違うタイプのワープ台を持つ 2 つの町の間はワープすることができ、ワープの際にたまる疲労度は以下の通りです。

  • タイプ 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
  • どの 2 つの町も、その間を直接結んでいる道路は多くとも 1 つ
  • どの 2 つの町も、いくつかの道路を辿って行き来できる
  • 入力は 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 から町 2 に (タイプ A からタイプ B へ) ワープし、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 から町 2 に (タイプ A からタイプ B へ) ワープし、更に町 2 から町 3 に (タイプ B からタイプ 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

Score : 6 points

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

There are N towns numbered 1 through N, and M roads. The i-th road connects Town A_i and Town B_i bidirectionally, and you get C_i points of fatigue when you pass through that road. For every pair of towns, there is at most one road that directly connects those towns, and it is possible to travel between those towns by traversing some roads. Additionally, each town has a teleporter of type A, type B, or type C. The placement of teleporters is given to you by a string S; the teleporter in Town i is of type S_i. There may be some types of teleporters that do not exist in any towns. You can teleport between two towns with different types of teleporters. When you do so, you get the following points of fatigue:

  • X_{\mathrm{AB}} points when teleporting between towns with teleporters of type A and type B;
  • X_{\mathrm{AC}} points when teleporting between towns with teleporters of type A and type C;
  • X_{\mathrm{BC}} points when teleporting between towns with teleporters of type B and type C.

You cannot teleport between towns with the same type of teleporter. Find the minimum possible total points of fatigue you get when going from Town 1 to Town N only using roads and teleporters.

Constraints

  • 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 is a string of length N consisting of A, B, and 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
  • For every pair of towns, there is at most one road that directly connects those towns.
  • For every pair of towns, it is possible to travel between those towns by traversing some roads.
  • All values in input, except S, are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Find the minimum possible total points of fatigue you get when going from Town 1 to Town N.

Sample Input 1

3 2
10 10 10
ABA
1 2 15
2 3 5

Sample Output 1

15

If you first teleport from Town 1 (type A) to Town 2 (type B) and then use the 2-nd road to go from Town 2 to Town 3, you get 10 + 5 = 15 points of fatigue, which is optimal. Note that both Town 1 and Town 3 have a teleporter of type A, so you cannot directly teleport between them.

Sample Input 2

3 2
10 1000000000 10
ABC
1 2 1000000000
2 3 1000000000

Sample Output 2

20

If you first teleport from Town 1 (type A) to Town 2 (type B) and from Town 2 (type B) to Town C (type C), you will get 10 + 10 = 20 points of fatigue, which is optimal. Note that you can teleport from Town 1 to Town 3 directly this time, but it is not optimal since teleporting from a teleporter of type A to that of type C costs X_{\mathrm{AC}} = 1000000000 points of fatigue.

Sample Input 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

Sample Output 3

8