グラフすごろく 2 Erlang(Beta)編（paizaランク A 相当）

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

問題

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

ここからグラフ上ですごろくを行います。
N 頂点 M 辺の DAG (非巡回有向グラフ) が与えられます。
i 番目の辺は頂点 U_i から頂点 V_i へ向かう有向辺です。
各頂点はすごろくのマスになっており、頂点 1 がスタートマス、頂点 N がゴールマスです。
その他の頂点は、所持金イベントマス、移動イベントマス、一回休みイベントマスのいずれかです。
移動イベントマスには正整数が設定されており、いまいる頂点から距離がその正整数分だけ離れた頂点に移動することができます。
ただし、頂点 i から頂点 j への距離が L であるとは、頂点 i から頂点 j へ向かう長さ L のパスが存在することを指します (最短パスである必要はありません)。
さらに、頂点 1 からどの頂点へも到達可能であり、どの頂点からも頂点 N へ到達可能であることが保証されます。

このグラフ上のある頂点 i から j マス進むとき、頂点 i から距離が j である好きなマスに移動することができます。
また、頂点 i からゴールマスへの距離が j 以下であるなら、ゴールマスに移動することもできます。

あなたはいまスタートマスである頂点 1 にいます。
サイコロは 1 ~ 6 の数字が等確率で出ます。
これから T ターンにわたってサイコロを振りすごろくをシミュレーションし、すごろくの出た目と各ターン後のマスの位置と所持金を出力してください。

入力される値

入力は以下のフォーマットで与えられます。

N M T
B_1 C_1
B_2 C_2
...
B_N C_N
U_1 V_1
U_2 V_2
...
U_M V_M

・1 行目には 3 つの整数 N, M, T が与えられます。
・続く N 行の i 行目には、頂点 i の i マス目の種類 B_i と数字 C_i が与えられます。
・続く M 行の i 行目には、U_i から頂点 V_i へ向かう有向辺を表す整数が空白区切りで与えられます。
・入力は N+M+1 行となり、末尾に改行が 1 つ入ります。

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

期待する出力: 期待する出力は T 行からなります。
i 行目には、i ターン目のサイコロの目と終了時のマス、所持金をこの順に空白区切りで出力してください。
ただし、i ターン目開始時にゴールマスにいる場合は Finished と出力してください。

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

・2 ≦ N ≦ 100
・1 ≦ M ≦ min(1000, N*(N-1)/2)
・1 ≦ T ≦ 20
・B_1 = "S" (スタートマス), C_1 = 0
・B_N = "G" (ゴールマス), C_N = 0
・B_i = "P" (所持金イベントマス) または "M" (移動イベントマス) または "Z" (一回休みイベントマス) (2 ≦ i ≦ N-1)
・B_i = "P" のとき、-100 ≦ C_i ≦ 100
・B_i = "M" のとき、1 ≦ C_i ≦ 10
・B_i = "Z" のとき、C_i = 0
・1 ≦ U_i, V_i ≦ N
・U_i ≠ V_i
・(U_i, V_i) ≠ (U_j, V_j) (i ≠ j)
・グラフは DAG であり、頂点 1 からどの頂点へも到達可能であり、どの頂点からも頂点 N へ到達可能である

入力例1: 5 5 3
S 0
Z 0
M 2
M 4
G 0
3 5
2 3
4 3
1 2
1 4

出力例1: 6 5 0
Finished
Finished

入力例2: 10 16 1
S 0
Z 0
P 57
P 45
M 7
Z 0
Z 0
P 33
P -65
G 0
1 3
1 8
1 10
4 2
4 7
3 2
2 9
2 10
8 7
8 6
7 9
7 5
6 10
1 4
9 5
5 10

出力例2: 6 10 0

入力例3: 15 18 3
S 0
P -84
Z 0
M 3
M 5
P -42
Z 0
Z 0
Z 0
Z 0
M 9
Z 0
P 59
Z 0
G 0
1 4
8 15
6 14
1 3
1 13
3 2
5 7
7 11
10 15
13 2
4 10
14 8
4 5
2 9
9 6
4 12
12 11
11 15

出力例3: 6 8 0
Skip
1 15 0

問題一覧へ戻る