Problemas
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≤N≤5⋅104) points of interest labeled 1…N, of which the first C (1≤C<N) are charging stations and the remainder are travel destinations. These points of interest are interconnected by M (1≤M≤105) bidirectional roads, the i-th of which connects distinct points ui and vi (1≤ui,vi≤N) and has length ℓi miles (1≤ℓi≤109).
A Bessla can travel up to 2R miles (1≤R≤109) 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≤K≤10) distinct charging stations. Your task is to assist Farmer John in identifying the set of well-connected travel destinations.
Entrada
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 ui, vi, and ℓi such that ui≠vi.
The charging stations are labeled 1,2,…,C. The remaining points of interest are all travel destinations.
Salida
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.
Ejemplo #1
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.
Ejemplo #2
4 3 2 101 2
1 2 1
2 3 100
1 4 10
2
3
4
Debes iniciar sesión para escribir código.