Moo Route II
플래티넘 V의견: 0
*Note: The time limit for this problem is 4s, twice the default.*
Bessie is on vacation! Due to some recent technological advances, Bessie will
travel via technologically sophisticated flights, which can even time travel.
Furthermore, there are no issues if two "parallel" versions of Bessie ever meet.
In the country there are \(N\) airports numbered \(1, 2, \ldots, N\) and \(M\)
time-traveling flights (\(1\leq N, M \leq 200000\)). Flight \(j\) leaves airport
\(c_j\) at time \(r_j\), and arrives in airport \(d_j\) at time \(s_j\)
(\(0 \leq r_j, s_j \leq 10^9\), \(s_j < r_j\) is possible). In addition, she must
leave \(a_i\) time for a layover at airport \(i\)
(\(1\le a_i\le 10^9\)).
(That is to say, if Bessie takes a flight arriving in airport \(i\) at time \(s\),
she can then transfer to a flight leaving the airport at time \(r\) if
\(r \geq s + a_i\). The layovers do not affect when Bessie arrives at an airport.)
Bessie starts at city \(1\) at time \(0\). For each airport from \(1\) to \(N\), what is
the earliest time when Bessie can get to at it?
Problem credits: Brandon Wang
SCORING
- Inputs 3-5: \(r_j < s_j\) for all \(j\), i.e. all flights arrive after they depart.
- Inputs 6-10: \(N, M \leq 5000\)
- Inputs 11-20: No additional constraints.
Problem credits: Brandon Wang
The first line of input contains \(N\) and \(M\).
The next \(M\) lines describe flights. The \(j\)th of these lines contains \(c_j\),
\(r_j\), \(d_j\), \(s_j\) in that order. (\(1\leq c_j, d_j \leq N\),
\(0\leq r_j, s_j \leq 10^9\))
The next line describes airports. It contains \(N\) space separated integers,
\(a_1, \ldots, a_N\).
There are \(N\) lines of output. Line \(i\) contains the earliest time when Bessie
can get to airport \(i\), or -1 if it is not possible for Bessie to get to that
airport.
3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 100
0
20Bessie can take the 3 flights in the listed order, which allows her to arrive at
airports 1 and 2 at time 0, and airport 3 at time 20.
Note that this route passes through airport 2 twice, first from time 10-11 and
then from time 0-1.
3 3
1 0 2 10
2 10 2 0
2 1 3 20
10 1 100
10
-1In this case, Bessie can take flight 1, arriving at airport 2 at time 10.
However, she does not arrive in time to also take flight 2, since the departure
time is 10 and she cannot make a 1 time-unit layover.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > February > Silver
평가 및 의견
Moo Route II
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Moo Route II