二回の枝移動での距離 Bash(Beta)編（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

ベルマンフォード法は、ある頂点からそのほかの各頂点への最短距離を更新していくアルゴリズムです。
この問題では、ある頂点から二回まで枝の移動が可能なときの各頂点への最短距離を求めてみましょう。

1,...,N の番号のついた N 個の頂点とそれらをつなぐ枝からなる有向グラフを考えます。ただし、自己ループと多重辺は考えません。

M 本の重み付き有向枝と頂点番号 s が与えられます。頂点 s から二回まで枝の移動が可能なときの、ほかのすべての頂点へ向かう経路の最短距離を出力してください。頂点 s から二回までの枝の移動では到達不可能な場合は inf と出力してください。

ただし、経路（枝の集合）の距離とはその経路を構成する枝の重みの和とします。ある頂点からその頂点自身へ移動する場合は、その区間の重みを 0 とします。

入力される値

N M s
a_1 b_1 c_1
...
a_M b_M c_M

1 行目に、頂点の個数を表す整数 N と、枝の本数を表す整数 M と、頂点の番号を表す整数 s が与えられます。

i + 1 行目に枝 i を表す整数の組 (a_i,b_i,c_i) が与えられます。枝 i は、頂点 a_i から頂点 b_i に向かう枝で、その重み（距離）は c_i です。(1 ≦ i ≦ M)

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 合計 N 行出力してください。j 行目には、二回まで枝の移動が可能なときの、頂点 s から頂点 j へ向かう経路の最短距離を出力してください (1 ≦ j ≦ N)。到達不可能な場合は inf と出力してください。

また末尾に改行をいれ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

入力はすべて整数

2 ≦ N ≦ 100

1 ≦ M ≦ N × (N-1)

1 ≦ s ≦ N

1 ≦ a_i, b_i ≦ N (1 ≦ i ≦ M)

a_i ≠ b_i (1 ≦ i ≦ M)

1 ≦ c_i ≦ 10 (1 ≦ i ≦ M)

同じ頂点の組（順序組）は 2 回以上入力されない

入力例1: 5 5 1
1 2 4
1 3 9
2 4 1
4 5 3
5 2 3

出力例1: 0
4
9
5
inf

入力例2: 5 7 1
1 2 4
1 3 9
2 4 1
4 5 3
5 2 2
2 3 6
1 5 3

出力例2: 0
4
9
5
3

入力例3: 4 4 1
1 2 1
2 3 3
1 4 2
4 3 4

出力例3: 0
1
4
2

問題一覧へ戻る