No.92 Escape Route
タグ : / 解いたユーザー数 297
作問者 :
sugim48
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もしくは右上の雲マークをクリックしてアカウントを作成してください。