Contest Duration: - (local time) (100 minutes) Back to Home

D - Shortest Path Queries 2 Editorial by en_translator

The problem is extracted from the essence of the algorithm called Floyd–Warshall algorithm.

For convenience, we define $$f(s,t,0)$$ as follows.

$f(s,t,0) = \begin{cases} 0 & s = t \\ \text{The weight of the edge }s\to t & \text{if the edge exists} \\ \mathrm{inf} & \text{if the edge doesn't exist} \end{cases}$

Now let us express $$f(s,t,k+1)$$ by means of $$f(\ast,\ast,k)$$. The shortest path on $$s \to t$$ when the vertices $$s$$, $$t$$, and those with index less than or equal to $$k+1$$ satisfies either of the following two conditions depending on whether or not it uses $$k+1$$. For each case, the shortest path can be calculated as follows.

• If $$k+1$$ is not used
• The only vertices available are $$s$$, $$t$$, and those less than or equal to $$k$$, so in this case the length of the shortest path is $$f(s,t,k)$$.
• If $$k+1$$ is used
• What we want is the shortest path from $$s$$ to $$k+1$$ only via those less than or equal to $$k$$, and that from $$k+1$$ to $$t$$ only via those less than or equal to $$k$$. Thus, the length of the shortest path is $$f(s,k+1,k) + f(k+1,t,k)$$.

Therefore, we have the following relations between $$f(s,t,k+1)$$ and $$f(\ast,\ast,k)$$.

$f(s,t,k+1) = \min(f(s,t,k) , f(s,k+1,k) + f(k+1,t,k))$

With the DP (Dynamic Programming) based on the recurrence relations above, we have solved the problems in a total of $$\mathrm{O}(N^3)$$ time.

Note that $$f(s, t, N)$$ is the length of the shortest path from $$s$$ to $$t$$ when all the vertices is allowed to path through. This way, the shortest path from $$s$$ to $$t$$ for all $$(s, t)$$ can be computed in a total of $$\mathrm{O}(N^3)$$ time; this is algorithm is called Floyd–Warshall algorithm.

A sample code in Python is pasted below.

import sys

d = [[1 << 60] * N for i in range(N)]
for i in range(N):
d[i][i] = 0
for a, b, c in zip(ABC, ABC, ABC):
d[a - 1][b - 1] = c