Let's solve the situation where, for some destination, there are multiple start nodes
and you need the shortest distance to the destination node.
(It doesn't matter which start node you leave from.)
(Edge costs are all non-negative and can be greater than 1.)
Normally you might think of the following strategy :
run Dijkstra from each start node to the destination node and compare all the shortest distances.
If we work out the time complexity, with
N: number of start nodes
V: number of nodes in the graph
E: number of edges in the graph
the time complexity is O(N E logV).
But with a really simple trick you can do it in O(ElogV).
In Dijkstra, the array storing shortest distances is defined as follows
f[n]: shortest distance from the start node to node n
But you can change this as follows.
f[n]: shortest distance to node n, considering all start nodes
Let's think about it.
Since Dijkstra uses a priority_queue, regardless of push order
it's guaranteed that the popped element is always the one with the shortest distance among the elements in the queue.
So even if you put multiple start nodes in at the beginning, it always pops the node with the shortest distance first, so
just by putting multiple starting points into the priority_queue and running Dijkstra
you can get the shortest distance considering multiple starting points.
You can apply this idea in this problem.