Problem F
Frantic Ferries
Fiona has a coding interview tomorrow at her dream company, Foogle (best known for their world-famous sorting engine), and of course she wants to arrive on time. However, she also wants to maximize her sleep (the more sleep she gets, the better the interview will go!). Therefore, she wants to leave at the latest possible time which still allows her to get to the interview. Since she is too busy brushing up for the interview to figure this out herself, she asks you for help.
Fiona has given you a map, which shows a number of junctions connected by two-way roads, and the amount of time it takes Fiona to drive along each road. Fiona’s house is at one junction, and the job interview is at another.
However, the best route to her interview may involve more than just roads! Fiona lives in Ferrydale, a prosperous coastal city famous for its fried fish, free furniture, fun fairs, and, of course, ferries, which are also shown on the map. Each ferry operates between two junctions, carrying passengers (and their cars) back and forth according to a fixed schedule. A ferry starts its first trip of the day at a set time, and after that it goes continuously back and forth between the two junctions, taking a certain amount of time $t_{\text {out}}$ to go from the first junction to the second, and a certain amount of time $t_{\text {in}}$ to return. (Note that $t_{\text {out}}$ and $t_{\text {in}}$ may be different due to prevailing currents.) The time taken to load and unload passengers in between trips is included in $t_{\text {out}}$ and $t_{\text {in}}$, so, for example, $t_{\text {out}}$ measures the amount of time from the instant the ferry departs on its outbound journey, through its arrival, unloading, and loading, until the instant it departs on its return journey.
Fiona can take any ferry in either direction, but she has to wait for its next trip in the direction she wants to go. Note that Fiona can still get on a ferry even if she arrives at a junction at the exact instant the ferry leaves. After disembarking from a ferry, she can continue driving along a connecting road (or get on another ferry) at the same instant that the ferry departs on its return trip, that is, the entire ferry trip takes exactly $t_{\text {in}}$ or $t_{\text {out}}$.
Given the information on the map and the time of Fiona’s interview, help her figure out the latest time she can possibly leave and still arrive at or before the time of her interview.
Input
The first line of the input consists of six space-separated integers $T$, $J$, $R$, $F$, $j_ F$, and $j_ I$.
-
$T$ is the time of the interview, with $0 \leq T \leq 10^9$.
-
$J$ is the number of junctions, with $2 \leq J \leq 10^4$ (the junctions are numbered from $0$ to $J-1$).
-
$R$ is the number of roads, with $0 \leq R \leq \min (10^4, \frac{J(J-1)}{2})$.
-
$F$ is the number of ferries, with $0 \leq F \leq \min (10^4, \frac{J(J-1)}{2})$.
-
$j_ F$ and $j_ I$ specify the locations of Fiona’s house and the interview, respectively ($0 \leq j_ F, j_ I < J$, and $j_ F \neq j_ I$).
After the first line follow $R$ lines, each containing a description of one road consisting of three space-separated integers $j_1$, $j_2$, and $t$, giving the junctions $j_1$ and $j_2$ connected by the road and the time $0 < t \leq 10^5$ Fiona needs to drive from one end of the road to the other (in either direction).
Finally there are $F$ lines each containing a description of one ferry. A ferry description consists of five space-separated integers:
-
$j_1$ and $j_2$ specify the junctions connected by the ferry;
-
$0 \leq d \leq 10^9$ is the time of the ferry’s first departure from $j_1$;
-
$0 < t_{\text {out}} \leq 10^5$ is the time the ferry takes to travel from $j_1$ to $j_2$;
-
$0 < t_{\text {in}} \leq 10^5$ is the time the ferry takes to travel back from $j_2$ to $j_1$.
No road or ferry ever connects a junction to itself, and every pair of junctions is connected by at most one road or ferry.
Although you do have to worry about the time of a ferry’s first departure, $d$—the ferry does not run at all prior to time $d$—you don’t have to worry about a ferry’s last departure, that is, you can assume that once it starts service, a ferry continues operating until at least the time of Fiona’s interview.
Output
Output a single line containing the latest time Fiona can leave her house and still arrive at or before the time of her interview. It is always be possible for Fiona to reach her interview by leaving at some time $t \geq 0$.
Explanation of sample inputs
In the first scenario, Fiona could drive to her interview in $15$ minutes, but it’s better for her to wait for the ferry which leaves at time $20$, getting her to the interview just on time.
In the second scenario, Fiona needs to get to her interview at time $40$. Since the ferries take $10$ and $5$ minutes to cross, respectively, one might think that she could wait to depart on the ferry from her house at time $20$. However, when she arrived at junction $1$ at time $30$, she would have just missed the second ferry, which departed at time $27$. She would have to wait for its next departure, at time $36$, but this would get her to the interview at time $41$, one minute late. Instead, she has to board the first ferry at time $0$, arriving at junction $1$ at time $10$, then wait for the second ferry’s next departure at time $18$, ultimately arriving $17$ minutes early for her interview.
| Sample Input 1 | Sample Output 1 |
|---|---|
30 3 2 1 0 2 0 1 10 1 2 5 0 2 20 10 10 |
20 |
| Sample Input 2 | Sample Output 2 |
|---|---|
40 3 0 2 0 2 0 1 0 10 10 1 2 0 5 4 |
0 |
