Problem F
Starsailer
You’re an engineer at the Homestead Company, a luxury
star-cruiser company that operates sleeper ships to and from
distant solar systems in the Milky Way galaxy. A few years ago,
there was an incident on the headlines - one of our ships
(namely, the Avalon) ran head-first into an asteroid field
large enough to overwhelm the ship’s shielding capabilities.
The ship sustained heavy damage and experienced an array of
cascading failures, which resulted in people waking up much
earlier than they should, among other things. While beefing up
the shields is one option, to do so without completely
re-designing the entire ship (which is a time-consuming and
expensive process!) would be a challenge.
Thus, in the meantime, the executives of the Homestead Company
would like you and your team of engineers to come up with a
system that, based on hazard-weighted inputs from the survey
team, tries to find how many solar systems will need to be
traveled through for the shortest route from origin to
destination, so that they will be able to decide whether a
particular route is feasible to operate or not.
Input
The first line contains an integer $a$ ($1 \le a \le 100$) the number of routes between two star systems to follow. The second line contains a string $b$, the solar system name where the ship will depart from. The third line contains a string $c$, the solar system name where the ship will travel to.
Subsequent input lines are $a$ pre-mapped, directed, path values that will be given as one line of $3$ space-separated values:
-
The first value in the line contains a string $x$, the origin solar system name
-
The second value in the line contains a string $y$, the destination solar system name
-
The third value in the line contains an integer $z$ ($1 \le z \le 200$) the hazard-weighted distance value for this specific route
Solar system name strings will never be longer than $16$ characters, and are case-insensitive. All input sets are guaranteed to have a valid path from origin to destination.
Output
Output the number of intermediate solar systems between origin and destination for the shortest path from origin to destination.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 Sun Polaris Sun Alpha 4 Alpha Polaris 3 Sun Polaris 8 |
1 |
