gold_Bessla_Motors (USACO February_Contest)
Time limit: 3 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: dijkstra, shortest path, graph theory

**Note: The time limit for this problem is 3s, 1.5x the default. The memory
limit for this problem is 512MB, twice the default.**
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 $2R$ 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.
INPUT FORMAT (input arrives from the terminal / stdin):
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.
OUTPUT FORMAT (print output to the terminal / stdout):
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.
SAMPLE INPUT:
3 3 1 4 1
1 2 3
1 3 5
2 3 2
SAMPLE OUTPUT:
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.
SAMPLE INPUT:
4 3 2 101 2
1 2 1
2 3 100
1 4 10
SAMPLE OUTPUT:
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.
SAMPLE INPUT:
4 3 2 100 2
1 2 1
2 3 100
1 4 10
SAMPLE OUTPUT:
1
4
SCORING:
Inputs 4 and 5: $K = 2$ and $N \le 500$ and
$M\le 1000$.
Inputs 6 and 7: $K = 2$.
Inputs 8-15: No additional constraints.
Problem credits: Alexander Wei

Starter code:

Grader code:

Setup script:

Evaluation script: