立ち寄り (paizaランク A 相当)

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

問題

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

今日は、paiza 君は塾の日で、paiza 君は地点 s にある家から地点 g にある塾へ向かいます。しかし、paiza 君はノートを使い切ってしまったため、塾へ行く前に地点 t にある文房具屋さんでノートを買う必要があります。paiza 君が家を出発して、文房具屋さんでノートを買い、塾へたどり着くまでの最短時間とその経路を出力してください。ただし、ノートを買う時間は考慮しないものとします。最短時間の経路が複数存在する場合は、そのうちのひとつを出力してください。家から文房具屋さんまでの道、または文房具屋さんから塾までの道が存在しない場合は、inf と出力してください。

入力される値

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

1 行目に、地点の個数を表す N と、それぞれの地点をつなぐ道の本数を表す整数 M と、地点の番号を表す整数 s, t, g が与えられます。

i + 1 行目に道 i を表す整数の組 (a_i,b_i,c_i) が与えられます。道 i は、地点 a_i から地点 b_i に向かう道で、その道の移動にかかる時間は c_i です。(1 ≦ i ≦ M)

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

期待する出力: 合計一行または二行出力してください。一行目に家から文房具屋さんを寄って塾へ到達するまでの最短時間を出力し、二行目にはその経路で辿る地点を順番に左から半角スペース区切りで出力してください。最短時間の経路が複数存在する場合はそのうちのひとつを出力してください。家から文房具屋さんまでの道、または文房具屋さんから塾までの道が存在しない場合は、一行で inf と出力してください。

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

条件

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

入力はすべて整数

3 ≦ N ≦ 100

1 ≦ M ≦ N × (N-1)

1 ≦ s,t,g ≦ N

s ≠ t ≠ g

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: 7 11 1 4 7
1 2 2
1 3 4
2 3 1
2 4 8
2 5 1
3 5 4
3 6 3
4 7 2
5 4 3
5 7 1
6 7 3

出力例1: 8
1 2 5 4 7

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

出力例2: inf

問題一覧へ戻る