No.92 逃走経路

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 156
作問者 : sugim48sugim48

4 ProblemId : 149 / 出題時の順位表

問題文

Yuki City は $N$ 個の町と $M$ 本の道路からなる。
町は $1$ から $N$ まで番号が振られている。
道路は双方向に通行でき、それぞれ通行料金が設定されている。

さて、Yuki City 警察のあなたはある指名手配犯を追っている。
長らく犯人の居場所を掴めなかったあなただが、つい先日有力な情報を手に入れた。
その情報とは、犯人が支払った通行料金のうち、直近 $K$ 回分を時系列順に並べたものである。
あなたはこの情報を使い、犯人が今いる可能性のある町を絞り込みたい。

警察官であると同時に天才プログラマーでもあるあなたは、プログラムによってこの問題を解こうと考えた。

入力

$N$ $M$ $K$
$a_1$ $b_1$ $c_1$
$\vdots$
$a_M$ $b_M$ $c_M$
$d_1$ $\ldots$ $d_K$

$1$ 行目に $N,M,K$ が空白区切りで与えられる。
続く $M$ 行に正整数 $a_i,b_i,c_i$ が空白区切りで与えられる。
これは、町 $a_i$ と町 $b_i$ が通行料金 $c_i$ の道路で結ばれていることを表す。
最終行に $K$ 個の正整数 $d_i$ が空白区切りで与えられる。
これは、犯人が支払った通行料金のうち、直近 $K$ 回分を時系列順に並べたものである。

$2\leq N\leq100$
$1\leq M,K\leq1,000$
$1\leq a_i<b_i\leq N$
$1\leq c_i,d_i\leq10^9$

出力

$1$ 行目に犯人が今いる可能性のある町の個数を出力せよ。
$2$ 行目にそのような町の番号を昇順に空白区切りで出力せよ。
最後に改行してください。

犯人が今いる可能性のある町は少なくともひとつ存在する。

サンプル

サンプル1
入力
3 2 2
1 2 10
2 3 20
10 20
出力
1
3

犯人は通行料金 $10$ の道路を通り、続いて通行料金 $20$ の道路を通った。
ここから犯人は今町 $3$ にいると分かる。

サンプル2
入力
3 2 2
1 2 10
1 2 20
10 20
出力
2
1 2

ある町のペアを複数本の道路が結ぶこともある。
また、どの町のペアも互いに行き来できるとは限らない。

提出ページヘ