問題一覧 > 通常問題

No.92 Escape Route

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 297
作問者 : sugim48
お気に入りにしたユーザー ProblemId : 149 / 自分の提出
問題文最終更新日: 2026-06-25 17:19:53
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 57 (順位表) の他の問題:

Problem Statement

Yuki City consists of $N$ towns and $M$ roads.
The towns are numbered from $1$ to $N$.
The roads can be traveled in both directions, and each has a toll set for it.

Now, you, a member of the Yuki City police, are pursuing a certain wanted criminal.
You had long been unable to determine the criminal's whereabouts, but just the other day you obtained a promising piece of information.
That information is the most recent $K$ tolls paid by the criminal, listed in chronological order.
Using this information, you want to narrow down the towns where the criminal could be now.

Being a genius programmer as well as a police officer, you decided to solve this problem with a program.

Input

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

Line $1$ contains $N,M,K$, separated by spaces.
Each of the following $M$ lines contains positive integers $a_i,b_i,c_i$, separated by spaces.
This means that town $a_i$ and town $b_i$ are connected by a road with toll $c_i$.
The last line contains $K$ positive integers $d_i$, separated by spaces.
These are the most recent $K$ tolls paid by the criminal, listed in chronological order.

$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$

Output

On line $1$, print the number of towns where the criminal could be now.
On line $2$, print the numbers of those towns in ascending order, separated by spaces.
Print a newline at the end.

There is at least one town where the criminal could be now.

Sample

Sample 1
Input
3 2 2
1 2 10
2 3 20
10 20
Output
1
3

The criminal traveled along a road with toll $10$, and then along a road with toll $20$.
From this, we can tell that the criminal is now in town $3$.

Sample 2
Input
3 2 2
1 2 10
1 2 20
10 20
Output
2
1 2

A pair of towns may be connected by multiple roads.
Also, it is not guaranteed that every pair of towns can reach each other.

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