**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
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
