(問題 30)回り道 5 Haskell(Beta)編（paizaランク S 相当）

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

問題

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

整数 N, M が与えられます。N 個の頂点と M 個の辺があるグラフを与えられます。

i (1 ≦ i ≦ M) 番目の辺は頂点 a_i と頂点 b_i を結んでいます。この辺は持っているスタンプの種類が c_i 個以下のときのみ通ることが出来ます。

また K 頂点の集合 S が与えられます。S に属する頂点のそれぞれに異なるスタンプが置かれています。スタンプが置かれている頂点に到達するとスタンプを押すか否かを入れぶことが出来ます。

頂点 1 から頂点 N にたどり着くことができるスタンプの種類数の最大値を A とします。A 種類のスタンプを回収しながら頂点 1 から頂点 N にたどり着くまでに必要な移動回数の最小値を求めてください。

入力される値

N M
a_1 b_1 c_1
a_2 b_2 c_2
...
a_M b_M c_M
K
S_1 S_2 ... S_K

1 行目には 2 つの整数 N, M が与えられます。

1 + i (1 ≦ i ≦ M) 行目には 3 つの整数 a_i, b_i, c_i が与えられます。

2 + M 行目には 1 つの整数 K が与えられます。

3 + M 行目には K 個の整数 S_1, S_2, ..., S_K が与えられます。

入力は合計で 3 + M 行からなり、入力値最終行の末尾に改行が 1 つ入ります。

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

期待する出力: 答えを 2 行で出力してください。

1 行目には A を、2 行目には A 種類のスタンプを回収しながら頂点 1 から頂点 N にたどり着くまでに必要な移動回数を出力してください。

条件

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

4 ≦ N ≦ 10000

1 ≦ M ≦ min(N × (N - 1) / 2, 200000)

1 ≦ a_i, b_i ≦ N (1 ≦ i ≦ M)

a_i ≠ b_i (1 ≦ i ≦ M)

0 ≦ c_i ≦ K (1 ≦ i ≦ M)

与えられるグラフは持っているスタンプが 0 種類のときには連結グラフ

1 ≦ K ≦ 5

2 ≦ S_i ≦ N - 1 (1 ≦ i ≦ K)

S_i ≠ S_j (1 ≦ i < j ≦ K)

入力例1: 5 5
1 2 1
2 4 1
4 3 1
3 5 0
5 1 1
1
3

出力例1: 1
6

入力例2: 4 3
1 3 2
2 3 2
1 4 0
2
2 3

出力例2: 0
1

問題一覧へ戻る