問題一覧 > 通常問題

No.92 逃走経路

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 300
作問者 : sugim48
8 ProblemId : 149 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:46:54

問題文

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

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

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

入力

N M K
a1 b1 c1

aM bM cM
d1  dK

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

2N100
1M,K1,000
1ai<biN
1ci,di109

出力

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

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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。