Bessla Motors
플래티넘 II의견: 0
*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.
Problem credits: Alexander Wei
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
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.
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.
3 3 1 4 1
1 2 3
1 3 5
2 3 21
2We 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.
4 3 2 101 2
1 2 1
2 3 100
1 4 102
3
4We 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.
4 3 2 100 2
1 2 1
2 3 100
1 4 101
4riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > February > Gold
평가 및 의견
Bessla Motors
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Bessla Motors