Train Ride III

Prereq: Train Ride II

It's been a month since you started working in Umbristan and all is going well. Like any developed nation Umbristan has been dabbling in new technologies and recently unveiled its newest invention the teleporter! The company heading the technology has also announced the locations where the teleporters will be placed. Some places will be at existing train stations, some at entirely new locations perhaps not serviceable by train. The company is charging a flat fare for use of any teleporter within one day so after the fee is paid you are free to use the teleporters as much as you want. The only disadvantage is that the teleporters only allow you to move to other teleporters. The teleporter company has also worked with the train company to place the teleporters such that it takes no time to move between trains and teleporters for the teleporters located at train stations. Another problem is that teleporters also have their own train station "lines". That is teleporters are given a numerical ID such that they can only teleport to other teleporters with the same ID. The teleporter company is still a start-up and trying to save money so each location has a maximum of 1 teleporter. The benefit is that this new technology may be able to improve your daily commute. You go back to the trusty map you drew up for Train Ride II and get to work planning your new transit route. Can you once again figure out the minimum price needed to get to your workplace on time?


This is a companion discussion topic for the original entry at https://algo.monster/problems/train_ride_3/