L - Journey of a Wizard

$f(x) = \begin{cases} x \div 2 & xが偶数 \\ x \times 2 & xが奇数\end{cases}$ 　とします。

$4N$ の頂点 $x_1, \ldots, x_N, y_1, \ldots, y_N, z_1, \ldots, z_N, w_1, \ldots, w_N$ を用意します。

まず道$i = (a_i, b_i, c_i)~(i = 1, \ldots, M)$ について、以下のように辺を張ります。

• $x_{a_i} \to x_{b_i}$ に重み $c_i$ の辺
• $y_{b_i} \to y_{a_i}$ に重み $c_i$ の辺
• $z_{a_i} \to z_{b_i}$ に重み $f(c_i)$ の辺
• $w_{b_i} \to w_{a_i}$ に重み $f(c_i)$ の辺

さらに、

$i = 1, \ldots, N$ について、

• $x_i \to y_i$ に重み $X$ の辺
• $x_i \to z_i$ に重み $Y$ の辺
• $y_i \to z_i$ に重み $Y$ の辺
• $z_i \to w_i$ に重み $X$ の辺

を張ります。

このグラフに対して、辺の張り方より以下が成り立ちます:

• $\{x_1, \ldots, x_N \}$ の誘導部分グラフは、魔法を使っていないときの国のグラフと一致する
• $\{y_1, \ldots, y_N \}$ の誘導部分グラフは、魔法1を使ったときの国のグラフと一致する
• $\{z_1, \ldots, z_N \}$ の誘導部分グラフは、魔法2を使ったときの国のグラフと一致する
• $\{w_1, \ldots, w_N \}$ の誘導部分グラフは、魔法1と魔法2を使ったときの国のグラフと一致する

魔法を一度も使っていない状態で頂点 $i$ にいて、魔法1を使うことを考えます。 魔法を一度も使っていない状態は、今考えているグラフで $x_i$ にいることに対応します。 魔法1を使うと、今考えているグラフで $y_i$ にいることに対応します。

つまり、「魔法を一度も使っていない状態で頂点 $i$ にいて、魔法1を使う」は、「$x_i \to y_i$ の重み $X$ の辺を通る」ことに対応します。 同様のことが $x_i \to z_i, y_i \to w_i, z_i \to w_i$ の辺についても言えます。

よって、このグラフについて $x_1$ からスタートし、$x_N, y_N, z_N, w_N$ まで移動するときの最短時間をそれぞれダイクストラ法を用いて計算し、そのうち最小のものが答えになります。

32bit整数で計算するとオーバーフローするケースが存在するので、64bit整数で計算する必要があります。