![]() |
|
2016年12月10日
E869120, square1001
|
JOI 国には N 個の街があり, それぞれ 1, 2, ..., N の番号が付けられている. また JOI 国には M 本の鉄道があり, それぞれの鉄道には 1, 2, ..., M の番号が付けられている.
i (1 ≦ i ≦ M) 本目の鉄道は, 街 Ai, 街 Bi, 街 Ci という 3 つの街を双方向に走っている. この鉄道の運賃は, 乗り始めと乗り終わる街を問わず Pi 円である.
今日は JOI 国で鉄道感謝祭という割引セールが開催されている. このセールの内容は以下の様なものである.
あなたは街 s に住んでいるので, このセールによって街 s から他の街に行くのにかかる最小の値段がいくらであるかが気になった. 街 s から他の街に行くために必要な値段の最小値を, それぞれの街について求めよ.
入力は M + 1 行からなる.
1 行目に, 3 つの整数 N, M, s (1 ≦ N ≦ 100,000, 1 ≦ M ≦ 200,000, 1 ≦ s ≦ N) が空白区切りで与えられる.
1 + i 行目 (1 ≦ i ≦ M) には, 4 つの整数 Ai, Bi, Ci, Pi (1 ≦ Ai, Bi, Ci ≦ N, 1 ≦ Pi ≦ 1,000,000,000) が空白区切りで入力される.
d(i, j) を街 i から j まで行くための最短コストとする. ただし, 街 i から街 j に鉄道を乗り継いで行くことが不可能である場合, d(i, j) = -1 とする.
このとき, i 行目 (1 ≦ i ≦ N) に d(s, i) を出力せよ.
入力例 1 | 入力例 2 |
---|---|
4 2 1 1 2 3 2 2 3 4 10 |
6 3 1 1 2 3 2 2 3 4 10 3 4 5 5 |
出力例 1 | 出力例 2 |
0 2 2 10 |
0 2 2 5 5 -1 |
入力例 1 では, 以下のようになる.
入力例 2 では, 以下のようになる.
※各入出力例のデータは,右クリック等によりファイルに保存して利用可能です.