Problem L
Speedy Delivery
The year is 2193, and Clarence lives in the sprawling Martian metropolis of New Conway, where he is a student at the Mars branch of Hendrix University. The views are stunning, although the downside is that it is not possible to see any solar eclipses.
In order to help pay for living expenses, Clarence works as a delivery person delivering small packages around town—picking up orders from stores and restaurants and delivering them to local residences. (Drone delivery has been strictly regulated since the drone rebellions of 2084.)
Because the lack of atmosphere restricts outside travel, the city of New Conway consists of a large number of domed hubs connected by monorails. Making a delivery requires Clarence to travel from hub to hub by transport pod until he reaches the pick-up point, then again until he reaches the drop-off point.
Clarence has a reputation as one of the fastest delivery people on New Conway thanks to a piece of advanced technology he managed to get his hands on: a personal teleportation device. Using this teleportation device, Clarence can instantly travel between hubs. However, before he can use the device he must first visit the hub he wants to travel to in-person and set that hub as the device’s destination. After doing that, at some later time he can instantly teleport back to the destination hub from anywhere in the city. Unfortunately, the teleporter can only support a single destination point; setting a new destination point causes the teleporter to forget the old destination point.
Input
Input for this problem begins with five integers: $n$, $s$, $p$, $d$, and $k$. The integer $n$ specifies the number of hubs, with $1 \le n \le 2\, 000$. The hubs are numbered from $1$ to $n$. The integer $s$ identifies the hub where Clarence is located at the beginning of the problem; $p$ is the hub where the package is to be picked up; and $d$ is the hub where the package is to be dropped off ($1 \leq s, p, d \leq n$). Finally, $k$ indicates the number of monorail lines that are available for Clarence to use, with $0 \leq k \leq 10^5$.
Following that are $k$ triples of integers $i$ $j$ $t$, each on a separate line, indicating that there is a monorail from hub $i$ to hub $j$, and that the trip takes $t$ minutes ($1 \leq t \leq 10^6$). The rails run both ways, so a connection between $i$ and $j$ can be used to go from $i$ to $j$ or from $j$ to $i$. The time is the same in either direction.
A monorail line that loops from a hub back to itself would be a pointless waste of money, as would having more than one monorail line between a given pair of hubs, so you can assume that each monorail line in the input is between a unique unordered pair of hubs $i$ and $j$, with $i \neq j$. You can also assume that it is always possible to reach any hub from any other hub via monorail.
Output
Output the smallest possible number of minutes in which the delivery can be completed.
You may assume that the time required to switch pods, to set the teleporter’s destination point, to teleport, to pick up the package, and to drop off the package are all negligible and thus count them as zero. The only times you need to consider are the times spent in transit between hubs.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 1 2 3 3 1 4 1 2 4 1 3 4 1 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 1 2 3 5 1 5 1 5 2 2 1 4 2 4 2 2 4 3 2 |
6 |
