Solution: Basic Graph Algorithms

Task

There are $n$ galaxies connected by $m$ intergalactic teleport-ways. Each teleport-way joins two galaxies and can be traversed in both directions. Also, each teleport-way $e$ has an associated cost of $c(e)$ dollars, where $c(e)$ is a positive integer. A teleport-way can be used multiple times, but the toll must be paid every time it is used. Judy wants to travel from galaxy $s$ to galaxy $t$, but teleportation is not very pleasant and she would like to minimize the number of times she needs to teleport. However, she wants the total cost to be a multiple of five dollars, because carrying small change is not pleasant either.

Analyze the given algorithm to compute the smallest number of times Judy needs to teleport to travel from galaxy $s$ to galaxy $t$ so that the total cost is a multiple of five dollars.

Logic building

To find the smallest number of times Judy needs to teleport from galaxy $s$ to galaxy $t$, so that the total cost is a multiple of five dollars, we can use a modified version of the Dijkstra’s algorithm. We will use $tuple (cost, count)$ to store the cost of teleporting and the count of teleports. The cost will be stored as a pair of integers: the cost modulo 5 and the actual cost.

Algorithm

• Create a dictionary $dist$ to store the minimum teleport count and cost for each galaxy. Initialize the distance from $s$ to itself as $(0, 0)$ and the distance to all other galaxies as ($float('inf'), float('inf'))$

...