怠け者の散歩 (Lazy Walks)
2人の友人は、移動時に消費するエネルギーについてとても慎重に計算しています。1人目の友人が隣の場所へ移動するときには
A のエネルギーを消費し、2人目の友人は隣の場所へ移動するときに B のエネルギーを消費します。ところが、2人が同じ場所にいるときには、どちらかがもう片方を運ぶことができ、その場合は2人分の移動を合わせて
A + B ではなく C のエネルギーで済ませることができます。ただし C は必ずしも A + B より小さいとは限らないため、運んだほうが常に得とは限りません。1人目の友人は場所1から出発し、2人目の友人は場所2から出発します。2人とも場所
n に到達し、しかも合計エネルギーの消費を最小に抑えたいと考えています。2人が場所 n へ到達するために必要なエネルギーの合計の最小値を求めてください。入力
最初の行には、3つの整数
A、B、C が与えられます (1 ≤ A, B, C ≤ 50 000)。次の行には、2つの整数
n と e (1 ≤ n, e ≤ 100 000) が与えられます。n は場所の数、e は接続の数です。続く
e 行には、各行に と が書かれており、これは場所 と場所 が直接つながっていることを意味します (1 ≤ ≤ n)。出力
2人が場所
n に到達するのに必要なエネルギー合計の最小値を出力してください。例
入力 | 出力 |
4 4 5
8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8 | 22 |
解説
友人1: 1 → 4 ⇒ 4
友人2: 2 → 3 → 4 ⇒ 8
2人一緒: 4 → 7 → 8 ⇒ 10
合計: 4 + 8 + 10 = 22
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB