Consider a directed graph \(G\) with \(N\) vertices that has an edge from \(u_t\) to \(v_t\) of weight \(t\) for each \(t = 1, 2, \ldots, T\) (but has no other edges).

Then, “Vertex \(v\) is a good vertex at time \(t\)” if and only if “one can reach on \(G\) from Vertex \(1\) to Vertex \(v\) by traversing edges with weights at most \(t\) exactly \(L\) times.”

Therefore, the answer for \(v = 1, 2, \ldots, N\) is equal to the answer for \(v = 1, 2, \ldots, N\) of the following question, respectively.

Find the minimum possible “maximum weight of edges in the path” when traveling on \(G\) from Vertex \(1\) to Vertex \(v\) by traversing edges exactly \(L\) times.

We solve this problem with Dynamic Programming (DP).

For each \(i = 0, 1, 2, \ldots, L\) and \(j = 1, 2, \ldots, N\), let us define \(\mathrm{dp}[i][j]\) by

\(\mathrm{dp}[i][v] := \) (the minimum possible “maximum weight of edges in the path” when traveling to Vertex \(v\) by traversing edges exactly \(i\) times).

Here, if it is impossible to reach Vertex \(v\) in exactly \(i\) moves, then we define \(\mathrm{dp}[i][v] = \infty\).

We consider the initial state of the DP. For \(v = 2, 3, \ldots, N\), by the definition of \(\mathrm{dp}[\ast][\ast]\),

\[\mathrm{dp}[0][v] = \infty.\]

Also, for convenience we define

\[\mathrm{dp}[0][1] = 0.\]

Next, we will describe the transitions of DP. For \(1 \leq i, j \leq N\), let \(W(i, j)\) be “the weight of the directed edge on \(G\) from Vertex \(i\) to Vertex \(j\).” If there does not exist such an edge, we let \(W(i, j) := \infty\).

Then, the recurrence relations of DP can be written as

\[ \begin{aligned} \mathrm{dp}[i][v] &= \displaystyle\min_{1 \leq u \leq N} \max \lbrace \mathrm{dp}[i-1][u], W(u, v) \rbrace\\ &= \min\lbrace \max\lbrace \mathrm{dp}[i-1][1] , W(1, v)\rbrace, \max\lbrace \mathrm{dp}[i-1][2] , W(2, v)\rbrace, \ldots, \max\lbrace \mathrm{dp}[i-1][N] , W(N, v)\rbrace \rbrace \end{aligned} \]

By computing \(\mathrm{dp}[i][\ast]\) in the order of \(i = 1, 2, \ldots, L\) based on the initialization and the transitions above, the answer for this problem is obtained as

\[\mathrm{dp}[L][1], \mathrm{dp}[L][2], \ldots, \mathrm{dp}[L][N].\]

However, this algorithm computes \(\mathrm{dp}[i][j]\) for \(NL\) pairs of \((i, j)\), which does not fit in the time limit. We will now describe how to optimize it.

Let us replace \(\max \lbrace a, b\rbrace\) with a multiplication \(a \cdot b\) and \(\min \lbrace a, b \rbrace\) with an addition \(a + b\); then the aforementioned DP transition

\[ \begin{aligned} \mathrm{dp}[i][v] &= \displaystyle\min_{1 \leq u \leq N} \max \lbrace \mathrm{dp}[i-1][u], W(u, v) \rbrace\\ &= \min\lbrace \max\lbrace \mathrm{dp}[i-1][1] , W(1, v)\rbrace, \max\lbrace \mathrm{dp}[i-1][2] , W(2, v)\rbrace, \ldots, \max\lbrace \mathrm{dp}[i-1][N] , W(N, v)\rbrace \rbrace \end{aligned} \]

can be written as

\[\begin{aligned} \mathrm{dp}[i][v] &= \displaystyle\sum_{u = 1}^N (\mathrm{dp}[i-1][u] \cdot W(u, v))\\ &= \mathrm{dp}[i-1][1]\cdot W(1, v) + \mathrm{dp}[i-1][2]\cdot W(2, v)+ \cdots + \mathrm{dp}[i-1][N]\cdot W(N, v), \end{aligned} \]

which can be formally written in the form of matrices as

\[\left[\begin{matrix} \mathrm{dp}[i][1] \\ \mathrm{dp}[i][2] \\\vdots \\ \mathrm{dp}[i][N]\end{matrix}\right] = \left[ \begin{matrix} W(1, 1)& W(2, 1) & \cdots & W(N, 1) \\ W(1, 2) & W(2, 2) & \cdots & W(N, 2) \\ \vdots & \vdots & \ddots & \vdots\\ W(1, N) & W(2, N) & \cdots & W(N, N) \\ \end{matrix}\right] \left[\begin{matrix} \mathrm{dp}[i-1][1] \\ \mathrm{dp}[i-1][2] \\\vdots \\\mathrm{dp}[i-1][N]\end{matrix}\right]. \]

Thus, let

\[\mathbf{A} := \left[\begin{matrix} W(1, 1)& W(2, 1) & \cdots & W(N, 1) \\ W(1, 2) & W(2, 2) & \cdots & W(N, 2) \\ \vdots & \vdots & \ddots & \vdots\\ W(1, N) & W(2, N) & \cdots & W(N, N) \\ \end{matrix}\right]\]

and for each \(i = 0, 1, 2, \ldots, L\) let

\[\mathbf{x}_i := \left[\begin{matrix} \mathrm{dp}[i][1] \\ \mathrm{dp}[i][2] \\\vdots \\\mathrm{dp}[i][N]\end{matrix}\right],\]

then for each \( i= 1, 2, \ldots, L\) we have

\[\mathbf{x}_i = \mathbf{A} \mathbf{x}_{i-1}.\]

Note that a multiplication is computed as \(\max\) and an addition is computed as \(\min\).

In order to find the answer for the problem \(\mathrm{dp}[L][1], \mathrm{dp}[L][2], \ldots, \mathrm{dp}[L][N]\), we want to obtain \(\mathbf{x}_L\); this can be written as

\[\mathbf{x}_L = \underbrace{\mathbf{A} (\mathbf{A} (\mathbf{A} (\ldots( \mathbf{A}}_L \mathbf{x}_0) \ldots))).\]

In general, even when the multiplication is \(\max\) and the addition is \(\min\), the associativity of multiplication of matrices holds:

\[(\mathbf{P}\mathbf{Q})\mathbf{R} = \mathbf{P}(\mathbf{Q}\mathbf{R}).\]

Therefore, we can write as

\[\mathbf{x}_L = \underbrace{\mathbf{A} (\mathbf{A} (\mathbf{A} (\ldots \mathbf{A}( \mathbf{A}}_L \mathbf{x}_0) \ldots))) = (\mathbf{A}^L)\mathbf{x}_0.\]

Hence, by computing \(\mathbf{A}^L\) with the fast exponentiation algorithm, where multiplication is computed as \(\max\) and addition as \(\min\), the problem can be solved in a total of \(\mathrm{O}(T+N^3 \log L)\) time.

Bonus

In general, if the addition and multiplication satisfies the axioms of semi-ring, then the associativity of multiplication of matrices holds, enabling us to optimize DP with the matrix exponentiation like described above.

A semi-ring is a set \(A\) equipped with two binary operations, addition \(+\) and multiplication \(\cdot\), such that all the following properties is satisfied:

• \((A, +)\) is an commutative monoid; i.e. it satisfies the following three conditions:

  • The associativity of \(+\) holds. That is, for any \(a, b, c \in A\), it holds that \((a+b)+c = a+(b+c)\).
  • There exists an identity \(0\) of \(+\). That is, there exists \(0 \in A\) such that \(a + 0 = 0+ a = a\).
  • The commutativity of \(+\) holds. That is, for any \(a, b \in A\), it holds that \(a + b = b + a\).

• \((A, \cdot)\) is a monoid; i.e. it satisfies the following two conditions:

  • The associativity of \(\cdot\) holds. That is, for any \(a, b, c \in A\), it holds that \((a\cdot b)\cdot c = a\cdot(b\cdot c)\).
  • There exists an identity \(1\) of \(\cdot\). That is, there exists \(1 \in A\) such that \(a \cdot 1 = 1\cdot a = a\).

• \(+\) and \(\cdot\) satisfies the following distributive property holds:

  • For any \(a, b, c \in A\), it holds that \(a \cdot (b + c) = a \cdot b + a \cdot c\).
  • For any \(a, b, c \in A\), it holds that \((a+b) \cdot c = a \cdot c + b \cdot c\).

• For all \(a \in A\), it holds that \(0 \cdot a = a \cdot 0 = 0\).

For example, \((A, +, \cdot)\) is a semi-group for each of the following cases:

• \(A := \R \cup \lbrace -\infty \rbrace\), addition \(+\) is \(\max\), and multiplication \(\cdot\) is an ordinary addition
• For a positive integer \(n\), \(A\) is a set of non-negative integer less than \(2^n\), \(+\) is bitwise logical sum, and \(\cdot\) is bitwise logical product
• For a positive integer \(n\), \(A\) is a set of non-negative integer less than \(2^n\), \(+\) is bitwise exclusive logical sum, and \(\cdot\) is bitwise logical product