L - Journey of a Wizard

2 secs 1024 MB
kusirakusira's icon kusirakusira

配点 : 300点

問題文

くしらっちょさんが住む国には NN 箇所の町があり、それぞれの町には 11 から NN の番号が割り振られています。また、町同士をつなぐ一方通行の道が MM 本あります。ii 番目の道は町 aia_i から町 bib_i へ移動することが可能で、その移動には cic_i 分かかります。

くしらっちょさんは魔法使いなので、次の2つの魔法を全体でそれぞれ 11 回まで、ある町の上にいるときに使うことができます。(魔法を使わなくてもよいです。また、どちらか一方のみ使ってもよいです。)

  • 魔法1: 唱えるのに XX 分かかる。MM 本ある道をすべて、かかる時間はそのままで逆向きにする。つまり、ii 番目の道は町 bib_i から町 aia_i へ、cic_i 分で移動できるようになり、町 aia_i から町 bib_i へは行けなくなる。

  • 魔法2: 唱えるのに YY 分かかる。ii 番目の道について、その移動にかかる時間を以下のように更新する。

    • cic_i が偶数のとき: cic_ici÷2c_i \div 2 に更新する。
    • cic_i が奇数のとき: cic_ici×2c_i \times 2 に更新する。

くしらっちょさんはいま頂点 11 にいます。頂点 NN まで最短で移動したとき、何分で移動できますか? 頂点 NNまで移動できない場合は -1 を出力してください。

制約

  • 2N5×1042 \leq N \leq 5 \times 10^4
  • 0M5×1040 \leq M \leq 5 \times 10^4
  • 1ai,biN1 \leq a_i, b_i \leq N1iM1 \leq i \leq M
  • 0ci1050 \leq c_i \leq 10^51iM1 \leq i \leq M
  • 0X,Y1050 \leq X, Y \leq 10^5
  • aibia_i \neq b_i
  • ij{ai,bi}{aj,bj}i \neq j \Rightarrow \{a_i, b_i\} \neq \{a_j, b_j\}
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

NN MM XX YY
a1a_1 b1b_1 c1c_1
\vdots
aMa_M bMb_M cMc_M

出力

11 行で、頂点 11 から頂点 NN までにかかる最短時間を出力してください。頂点NNに到達できない場合、-1を出力してください。

入力例1

入力
3 2 10 100
1 2 5
3 2 10
出力
25
  • 頂点 11 から頂点22に移動する。55 分かかる。
  • 頂点 22 で魔法11を唱える。1010 分かかる。
  • 頂点 22 から頂点33に移動する。1010 分かかる。

とすると、最短で頂点 11 から頂点 33 に移動できて、合計 2525 分かかります。

入力例2

入力
3 2 10 1
1 2 5
3 2 10
出力
21
  • 頂点 11 から頂点 22 に移動する。55 分かかる。
  • 頂点 22 で魔法 11 を唱える。1010 分かかる。
  • 頂点 22 で魔法 22 を唱える。11 分かかる。
  • 頂点 22 から頂点 33 に移動する。55 分かかる。

とするのが最短で、合計 2121 分かかります。同じ頂点で魔法1と魔法2を唱えてもよいです。

入力例3

入力
5 5 1 1
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1
出力
-1

どのようにしても頂点 11 から頂点 55 に移動できません。-1を出力してください。

入力例4

入力
7 10 6 13
1 4 10
1 5 3
1 6 4
4 2 10
4 3 5
4 6 6
5 4 2
5 6 5
6 1 9
7 5 9
出力
18

提出


Go (1.21)