AT_past202010_j ワープ

[problemUrl]: https://atcoder.jp/contests/past202010-open/tasks/past202010_j $ 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 $ へ道路とワープのみを使って行く際に合計でたまる疲労度の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ へ行く際に合計でたまる疲労度の最小値を出力せよ。

### 注意 この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 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 $ 以外全て整数 ### Sample Explanation 1 まず町 $ 1 $ から町 $ 2 $ に (タイプ A からタイプ B へ) ワープし、$ 2 $ 番目の道路を使って町 $ 2 $ から町 $ 3 $ へ行くと、$ 10\ +\ 5\ =\ 15 $ の疲労度で到達でき、最適です。 町 $ 1 $ と町 $ 3 $ は両方タイプ A のワープ台があるので直接ワープすることはできないことに注意してください。 ### Sample Explanation 2 町 $ 1 $ から町 $ 2 $ に (タイプ A からタイプ B へ) ワープし、更に町 $ 2 $ から町 $ 3 $ に (タイプ B からタイプ C へ) ワープすると $ 10\ +\ 10\ =\ 20 $ の疲労度で到達でき、最適です。 この場合町 $ 1 $ から町 $ 3 $ に直接ワープ可能ですが、タイプ A から タイプ C へのワープのため $ X_{\mathrm{AC}}\ =\ 1000000000 $ の疲労度がかかるので最適ではありません。