2029: [USACO 2024 February Contest Gold] Problem 1. Bessla Motors

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.

The charging stations are labeled $1,2,\dots ,C$. The remaining points of interest are all travel destinations.

3 3 1 4 1
1 2 3
1 3 5
2 3 2

1
2