グラフすごろく 1 Perl編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
ポスト
下記の問題をプログラミングしてみよう！
ここからはグラフ上ですごろくを行います。
N 頂点 M 辺のグラフが与えられます。
i 番目の辺は頂点 U_i から頂点 V_i へ向かう有向辺です。
グラフは DAG (非巡回有向グラフ) であることが保証されます。
各頂点はすごろくのマスになっており、頂点 1 がスタートマス、頂点 N がゴールマスです。
さらに、頂点 1 からどの頂点へも到達可能であり、どの頂点からも頂点 N へ到達可能であることが保証されます。
あなたはいまスタートマスである頂点 1 にいます。
サイコロを振ったところ L がでました。
頂点 1 からの距離がちょうど L である頂点をすべて出力してください。(そのようなマスが 1 つ以上存在することが保証されます。)
頂点 1 から頂点 i への距離が L であるとは、頂点 1 から頂点 i へ向かう長さ L のパスが存在することを指します (最短パスである必要はありません)。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N M L
U_1 V_1
U_2 V_2
...
U_M V_M
・1 行目には 3 つの整数 N, M, L が与えられます。
・続く M 行の i 行目には、U_i から頂点 V_i へ向かう有向辺を表す整数が空白区切りで与えられます。
・入力は M+1 行となり、末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
頂点 1 からの距離がちょうど L であるすべての頂点を空白区切りで 1 行に出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・2 ≦ N ≦ 100
・1 ≦ M ≦ N*(N-1)/2
・1 ≦ L ≦ N - 1
・1 ≦ U_i, V_i ≦ N
・U_i ≠ V_i
・(U_i, V_i) ≠ (U_j, V_j) (i ≠ j)
・グラフは DAG であり、頂点 1 からどの頂点へも到達可能であり、どの頂点からも頂点 N へ到達可能である
・頂点 1 からの距離がちょうど L である頂点が 1 つ以上存在する
- 入力例1
-
5 6 2
1 2
1 3
4 2
1 4
2 5
3 5
- 出力例1
-
2 5
- 入力例2
-
10 27 2
1 8
1 9
1 3
1 2
1 5
8 3
8 5
8 6
8 10
9 2
9 5
9 4
9 10
3 2
3 7
3 5
2 5
2 4
2 10
7 5
7 4
7 6
7 10
5 6
5 10
6 10
4 10
- 出力例2
-
2 3 4 5 6 7 10
- 入力例3
-
15 17 2
2 6
6 4
5 11
9 8
10 13
4 14
7 9
12 3
14 15
13 11
8 15
10 7
3 8
10 5
2 10
11 12
1 2
- 出力例3
-
6 10
