No.3393 Move on Highway
タグ : / 解いたユーザー数 30
作問者 :
yu23578
/ テスター :
GaLLium
yt142857
aa36
Germanium32
問題文
yu23578王国には $1$ から $N$ までの番号がついた $N$ 個の街と $1$ から $M$ までの番号がついた $M$ 本の高速道路があります。高速道路 $i$ は街 $u_i$ と街 $v_i$ を双方向に結んでおり、コストは $w_i$ です。
yu23578君は街 $1$ から街 $N$ まで、高速道路を車で移動するにしました。高速道路を利用する際には、以下の料金がかかります。
- 高速道路 $i$ を利用する度、ガソリン代として $w_i$ 円かかる。
- 街 $N$ に着いたとき、高速料金として (道路を利用した合計回数) $\times C$ 円かかる。
$i = 2,3,\cdots,N$ に対して以下の問題を解いてください。
- 街 $i$ を訪れると、初めて訪れた時のみクーポンを $1$ 枚取得する。以降、高速道路を利用する際にクーポンを $1$ 枚消費することで、一度だけガソリン代を免除することが出来る。ただし、高速料金は請求される。また、街 $i$ を訪れなくても良い。
この時、街 $1$ から街 $N$ まで移動する際にかかる料金の最小値を解答してください。
制約
- $2 \le N \le 2 \times 10^5$
- $N-1 \le M \le \mathrm{min}(\frac{N(N-1)}{2},2 \times 10^5)$
- $1 \le C \le 10^9$
- $1 \le u_i < v_i \le N$
- $i \neq j$ ならば $(u_i,v_i) \neq (u_j,v_j)$
- $1 \le w_i \le 10^9$
- 街 $1$ からいくつかの道路を経由してすべての街に行くことが出来る。
- 入力はすべて整数
入力
$N\ M\ C$ $u_1\ v_1\ w_1$ $u_2\ v_2\ w_2$ $\vdots$ $u_M\ v_M\ w_M$
出力
$N-1$ 行出力してください。 $x$ 行目には $i=x+1$ の時の答えを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 3 1 1 2 1 1 3 3 2 3 4
出力
3 4
以下に $i = 2$ の時の移動の一例を示します。
街 $1$ から街 $2$ へ移動する。現在のガソリン代の合計は $1$ 円で、チケットを $1$ 枚持っている
街 $2$ から街 $3$ へ移動する。チケットを利用することで、現在のガソリン代の合計は $1 + 0 = 0$ 円に抑えられる。
この時、利用した道路の本数は $2$ 本なので、高速料金として $1 \times 2 = 2$ 円請求される。最終的な料金は $1+2=3$ 円である。
また、 $i = 3$ の時の移動の一例は以下のとおりです。
街 $1$ から街 $3$ へ移動する。現在のガソリン代の合計は $3$ 円で、チケットを $1$ 枚持っている。
この時、利用した道路の本数は $1$ 本なので、高速料金として $1 \times 1 = 1$ 円請求される。最終的な料金は $3+1=4$ 円である
この移動のように、チケットを使わずに街 $N$ についても構いません。
サンプル2
入力
5 5 1000000000 1 2 1 2 3 1 3 4 1 4 5 1 1 5 1
出力
1000000001 1000000001 1000000001 1000000001
いかなる $i$ でも、明らかに街 $1$ から街 $5$ まで直接行くのが最適です。
サンプル3
入力
7 9 338371223 1 2 284635923 2 3 183265394 6 7 119364529 5 7 998244353 5 6 763194723 2 5 563252789 2 4 345438454 4 5 683742211 3 5 332485634
出力
1863002381 2153871843 2667301480 1863002381 2861246734 2861246734
出力が32bit整数に収まらないこともあります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。