どっちが近い？ (paizaランク A 相当)

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

問題

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

paiza 国には 1 から n までの番号がついた n 個の地点と、それらを結ぶ m 本の道路があります。
i 番目の道路は、地点 a_i と地点 b_i を結んでいて、その距離は 5 km です。

今回、paiza 国では 2 つの避難場所をつくることにしました。
避難場所はそれぞれ地点 x, y にあります。

各地点について、地点 x までの最短距離と、地点 y までの最短距離のどちらが短いかを求めてください。

入力される値

n m x y
a_1 b_1
...
a_m b_m

・ 1 行目に、地点の個数を表す整数 n, 道路の本数を表す整数 m, 避難場所の地点を表す整数 x, y が半角スペース区切りで与えられます。
・続く m 行では、地点の番号の組 a_i, b_i が半角スペース区切りで与えられます。(1 ≦ i ≦ m)

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

期待する出力: 合計 n 行出力してください。

i 行目には、地点 i から地点 x までの最短距離のほうが短い場合には X is closer, 地点 i から地点 y までの最短距離のほうが短い場合には Y is closer, どちらも同じ場合には Same を出力してください。

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

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

・入力はすべて整数
・ 2 ≦ n ≦ 100,000 = 10^5
・ n - 1 ≦ m ≦ min(n × (n - 1) / 2, 100,000 = 10^5)
・ 1 ≦ x, y ≦ n
・ x ≠ y
・ 1 ≦ a_i, b_i ≦ n
・ a_i ≠ b_i
・ (a_i, b_i) ≠ (a_j, b_j), (a_i, b_i) ≠ (b_j, a_j) (i ≠ j)
・与えられるグラフは連結である

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

出力例1: X is closer
Same
Y is closer

問題一覧へ戻る