2 頂点間の最短経路（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
木を構成する 1 〜 N の番号がつけられた頂点とそれらを結ぶ辺の情報と頂点番号 X, Y が与えられます。
頂点 X から 頂点 Y へ最短経路で移動したときに通過する頂点の番号を X , Y を含めて通る順に出力してください。
なお、木における 2 頂点間の最短経路は一意に定まることが保証されています。
--- ヒント ---
2 頂点間の距離を求める幅優先探索では、「頂点 X からの距離が i である頂点」から「頂点 X からの距離が i+1 である頂点」を求めていました。
この求める情報に経路を追加することで同様に幅優先探索でこの問題を解くことができます。
具体的には、「頂点 X からの距離が i である頂点までの経路」を元に「頂点 X からの距離が i+1 である頂点までの経路」を求める幅優先探索を、Y に到達するまで行ってみましょう。
- 入力される値
-
N X Y
a_1 b_1
...
a_{N-1} b_{N-1}
・ 1 行目では、頂点の数 N と、頂点番号 X, Y が半角スペース区切りで与えられます。
・ 続く N-1 行では、N-1 個の辺の両端の頂点の番号 a_i, b_i (1 ≦ i ≦ N-1) が与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
・頂点 X から 頂点 Y へ最短経路で移動したときに通過する頂点の番号を X , Y を含めて通る順に改行区切りで出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 100,000
・1 ≦ X, Y ≦ N
・X ≠ Y
・1 ≦ a_i, b_i ≦ N (1 ≦ i ≦ N-1)
・a_i ≠ b_i (1 ≦ i ≦ N-1)
- 入力例1
-
5 1 5
1 3
3 2
3 4
4 5
- 出力例1
-
1
3
4
5
- 入力例2
-
7 5 2
7 5
5 6
1 5
1 4
1 2
1 3
- 出力例2
-
5
1
2
