アリスはすっかり退屈していました。いつも一緒に遊んでいる白ウサギが、トランプ城へ出かけているからです。（あーあ、こんなことなら一緒に出かければよかったわ。）とアリスは思いました。けれども、ここは歪みの国。そうやすやすと出かけては、ひどく疲れてしまいます。どういうことかというと—
白ウサギは困っていました。トランプ城への道中、ちょっとだけ道を間違えてしまったのです。（困ったなあ。一度戻って、道を良く知っているアリスに案内してもらうことにしよう。）と白ウサギは考えました。それにしても、白ウサギはとっても疲れているみたい。白ウサギは懐中時計を見ながら、
「なんだってこの国の道は、通る度に長さが変わったように感じるんだ！この道、さっきは100メートルくらいに感じたけど、今度は1キロはあるんじゃないか？それも、通り抜けるのにかかる時間はほとんど変わってないって言うのに！」
と叫んでいます。そう、ここは歪みの国。まさに、時々刻々と道が歪み続ける不思議な国なのです。 やっとの思いでアリスの家に着いた白ウサギが開口一番、
「ごめんよアリス。トランプ城まで、道案内をお願いできるかい。」
と言うと、退屈のあまりオフトゥンに突っ伏してしていたアリスは元気に飛び起きました。
「もちろんよ！一緒に行きましょう！」
嬉しい一方で、疲れた様子の白ウサギを見て（でも、あまりに疲れてしまうのは悪いわね。）と思ったアリスは、家の奥から歪みの国の地図を取り出してきました。
「さあ、トランプ城までの疲れない道のりを探すわ！」
n頂点とm辺からなる無向グラフが与えられる。各辺iの移動にかかる時間はt_iで表される。また、初めの体感移動速度としてv_0が与えられる。その後、辺を1本通る度に体感移動速度が変化する。辺をj本通った後の体感移動速度は、整数a, b, cをパラメータとして以下の式で与えられる。
v_j = (a \times v_{j-1} + b) mod c
辺iを速度v_jで通ると体感移動距離がt_i \times v_jとなる。なお、歪みの国では体感移動速度が0でも移動可能であり、そのときの体感移動距離は0である。
今、頂点1から出発し頂点nを経由して頂点1に戻ってくるような経路を考える。考えうる経路の中で体感移動距離の総和を最小化せよ。
n m x_1 y_1 t_1 ... x_m y_m t_m v_0 a b c
入力は全て整数からなる。 1行目には、グラフの頂点数と辺数を表すn,mがこの順で空白区切りで与えられる。 続くm行のうちi行目には、i番目の辺が接続する2頂点x_i,y_iと、通過するのにかかる時間t_iがこの順で空白区切りで与えられる。 m+2行目には、初速度を表すv_0が与えられる。 m+3行目には、速度の計算式のパラメータa,b,cがこの順に空白区切りで与えられる。
体感移動距離の総和の最小値を1行に出力せよ。
4 4 1 2 3 2 3 1 2 4 5 3 4 2 5 4 5 6
34
6 5 1 2 1 2 3 100 3 4 2 4 5 200 5 6 1 3 4 5 9
341
通過するのに時間がかかる辺 (2,3) と (4,5) を通る前に、短い時間で通れる道を往復して、なるべく速度を落とした方が体感移動距離は短い。
10 9 1 2 74150933 2 3 13214145 3 4 45636411 4 5 90778512 5 6 85676138 6 7 60913535 7 8 43917556 8 9 47519690 9 10 56593754 33 37 41 47
23049391759
体感移動距離が非常に長くなる場合もある。