| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 185 | 53 | 48 | 30.189% |
Farmer John would like to promote his line of Bessla electric tractors by showcasing Bessla's network of charging stations. He has identified $N$ (2ドル\le N\le 5\cdot 10^4$) points of interest labeled 1ドル\dots N,ドル of which the first $C$ (1ドル\le C < N$) are charging stations and the remainder are travel destinations. These points of interest are interconnected by $M$ (1ドル\le M\le 10^5$) bidirectional roads, the $i$-th of which connects distinct points $u_i$ and $v_i$ (1ドル\le u_i, v_i\le N$) and has length $\ell_i$ miles (1ドル\le\ell_i\le 10^9$).
A Bessla can travel up to 2ドルR$ miles (1ドル\le R\le 10^9$) on a single charge, allowing it to reach any destination within $R$ miles of a charging station. A destination is deemed well-connected if it is reachable from at least $K$ (1ドル\le K\le 10$) distinct charging stations. Your task is to assist Farmer John in identifying the set of well-connected travel destinations.
The first line contains five space-separated integers $N,ドル $M,ドル $C,ドル $R,ドル and $K$. Each of the following $M$ lines contains three space-separated integers $u_i,ドル $v_i,ドル and $\ell_i$ such that $u_i\neq v_i$.
The charging stations are labeled 1,ドル 2, \ldots, C$. The remaining points of interest are all travel destinations.
First, output the number of well-connected travel destinations on a single line. Then, list all well-connected travel destinations in ascending order, each on a separate line.
3 3 1 4 1 1 2 3 1 3 5 2 3 2
1 2
We have one charging station at 1ドル$. From this charging station, we can reach point 2ドル$ (since it is distance 3ドル$ away from 1ドル$), but not point 3ドル$ (since it is distance 5ドル$ away from 1ドル$). Thus, only point 2ドル$ is well-connected.
4 3 2 101 2 1 2 1 2 3 100 1 4 10
2 3 4
We have charging stations at 1ドル$ and 2ドル,ドル and both points 3ドル$ and 4ドル$ are within distance 101ドル$ of both 1ドル$ and 2ドル$. Thus, both points 3ドル$ and 4ドル$ are well-connected.
4 3 2 100 2 1 2 1 2 3 100 1 4 10
1 4