
USACO 2024 February Contest, Gold
Problem 1. Bessla Motors
Contest has ended.

Log in to allow submissions in analysis mode
**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≤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.
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 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.
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≤500 and M≤1000.
- Inputs 6 and 7: K=2.
- Inputs 8-15: No additional constraints.
Problem credits: Alexander Wei