Party - 1238
Dijkstra is an algorithm that finds the shortest distance from one point to every other point.
In this problem, we need to find
A. all the shortest distances from X to every other point, and
B. the shortest distance from every other point to X.
( It's not a bidirectional graph, so the cost of going and coming back can differ )
A can be solved with one run of Dijkstra.
But for B, you have to run Dijkstra a total of N-1 times, from every other point.
Calculating the time complexity, one Dijkstra run is O(MlogN), and running it N times in total
gives a time complexity of O(NMlogN).
Plugging in N, M, NMlogN ≒ 10001000010- = 100 million-.
So since 100 million operations take about 1 second, it does meet the problem's time limit, but it's a bit borderline.
Here, let's take away the idea of a reverse graph.
A reverse graph is a graph where all the edge directions of the original graph are flipped.
Say there's a graph where the shortest distance from A to B is X.
If you flip all the edge directions of this graph, only the directions change and all the connection points of the edges stay the same,
so it's obvious that the shortest distance from B to A is X.
Applying this logic to the problem, the shortest distance from every other point to X in the original graph
is the same as the shortest distance from X to every other point in the reverse graph.
In other words, in the reverse graph, you can get the shortest distance to every other point with one Dijkstra run from X.
You can get the shortest distance to X and the shortest distance from X with just two Dijkstra runs.
The time complexity is O(2MlogN) = O(MlogN) = 10000*10- = 100000- , so
it got about 100 times faster.