グラフすごろく3 Rust(Beta)編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
ポスト
下記の問題をプログラミングしてみよう！
N 頂点 M 辺の DAG (非巡回有向グラフ) が与えられます。
i 番目の辺は頂点 U_i から頂点 V_i へ向かう有向辺です。
各頂点はすごろくのマスになっており、頂点 1 がスタートマス、頂点 N がゴールマスです。
その他の頂点は、所持金イベントマス、移動イベントマス、一回休みイベントマスのいずれかです。
このグラフ上のある頂点 i から j マス進むとき、頂点 i から距離が j である好きなマスに移動することができます。
また、頂点 i からゴールマスへの距離が j 以下であるなら、ゴールマスに移動することもできます。
K 人のプレイヤーですごろくを行います。
最初すべてのプレイヤーはスタートマスである頂点 1 にいます。
サイコロは 1 ~ 6 の数字が等確率で出ます。
これから T ターンにわたってサイコロを振りすごろくをシミュレーションし、すごろくの出た目と各ターン後の各プレイヤーのマスの位置と所持金を出力してください。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N M T K
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 行目には 4 つの整数 N, M, T, K が与えられます。
・続く N 行の i 行目には、頂点 i の i マス目の種類 B_i と数字 C_i が与えられます。
・続く M 行の i 行目には、U_i から頂点 V_i へ向かう有向辺を表す整数が空白区切りで与えられます。
・入力は N+M+1 行となり、末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
期待する出力は T × K 行からなります。
各ターンの出力はプレイヤー 1 から順に、プレイヤーの番号とすごろくの目、ターン終了時のマス、所持金を空白区切りで出力します。
ただし、そのターン一回休みのプレイヤーはプレイヤーの番号とSkipを出力してください。
また、ターン開始時にゴールマスにいるプレイヤーは、プレイヤーの番号とFinishedを出力してください。
これを 1, 2, ..., T ターンの順に出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・2 ≦ N ≦ 100
・1 ≦ M ≦ min(1000, N*(N-1)/2)
・1 ≦ T ≦ 20
・2 ≦ K ≦ 10
・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 9 4 3
S 0
Z 0
P 18
P 12
G 0
1 3
1 4
1 2
3 4
3 2
3 5
4 2
4 5
2 5
- 出力例1
-
1 6 5 0
2 1 4 12
3 3 2 0
1 Finished
2 2 5 12
3 Skip
1 Finished
2 Finished
3 6 5 0
1 Finished
2 Finished
3 Finished
- 入力例2
-
10 17 5 5
S 0
M 5
M 4
M 5
M 9
Z 0
Z 0
Z 0
Z 0
G 0
1 8
1 3
4 10
8 6
8 9
8 2
8 3
5 6
5 3
6 10
3 10
9 10
1 4
1 5
2 3
7 10
5 7
- 出力例2
-
1 6 10 0
2 1 10 0
3 2 10 0
4 6 10 0
5 5 10 0
1 Finished
2 Finished
3 Finished
4 Finished
5 Finished
1 Finished
2 Finished
3 Finished
4 Finished
5 Finished
1 Finished
2 Finished
3 Finished
4 Finished
5 Finished
1 Finished
2 Finished
3 Finished
4 Finished
5 Finished
- 入力例3
-
15 20 3 8
S 0
P -79
P 44
P 85
Z 0
M 10
Z 0
Z 0
M 9
M 6
Z 0
P 89
Z 0
M 2
G 0
9 7
13 5
4 7
4 12
4 8
6 2
8 15
10 15
1 13
14 3
2 8
1 14
11 12
13 4
1 9
5 10
12 6
7 8
4 11
3 15
- 出力例3
-
1 6 2 -79
2 1 15 0
3 2 4 85
4 2 3 44
5 6 15 0
6 5 2 -79
7 5 15 0
8 1 15 0
1 2 15 -79
2 Finished
3 5 8 85
4 6 15 44
5 Finished
6 2 15 -79
7 Finished
8 Finished
1 Finished
2 Finished
3 Skip
4 Finished
5 Finished
6 Finished
7 Finished
8 Finished
