経由点の選択 Python3編（paizaランク B 相当）

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

問題

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

ワーシャルフロイド法では、各頂点に対して、その頂点を経由するとある 2 点間を結ぶ経路の距離が短くなるかどうかを考えます。本問では、ある 2 点間の距離を最短とする経由点を求めてみましょう。

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

頂点 X と Y が与えられます。その後、M 本の重み付き有向枝が与えられます。ただし、ここで与えられる枝はすべて、X から Y 以外の頂点へ向かう枝、または X 以外の頂点から Y へ向かう枝のどちらかです。

このとき、X から Y へ向かう経路のうち、その距離が最短となる経路の経由点を出力してください。距離が最短となる経路が複数存在する場合は、それらの経由点全てを昇順で出力してください。X から Y へ向かう経路が存在しない場合は 999 と出力してください。

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

入力される値

N M X Y 
a_1 b_1 c_1
...
a_M b_M c_M

1 行目に、頂点の個数を表す整数 N と、枝の本数を表す整数 M と、始点を表す X と、終点を表す Y が与えられます。

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

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

期待する出力: 1 行で出力してください。最短となる経路が複数存在する場合は、それらの経由点全てを左から昇順で半角スペース区切りで出力してください。X から Y へ向かう経路が存在しない場合は 999 と出力してください。

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

条件

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

入力はすべて整数

4 ≦ N ≦ 100

1 ≦ M ≦ 2 * (N-2)

1 ≦ X, Y ≦ N

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

a_i = X または b_i = Y のどちらか 1 つだけが必ず成り立つ (1 ≦ i ≦ M)

a_i ≠ b_i (1 ≦ i ≦ M)

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

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

出力例1: 2

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

出力例2: 2 3 4

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

出力例3: 999

問題一覧へ戻る