DP - Shortest paths: Acyclic formulation - Competitive Programming

DP - Shortest paths: Acyclic formulation

In the previous task, we say a DP formulation for the shortest path problem with positive edge weights \(w\) from a given source node \(s\):

\begin{equation*} dp(s) = 0 \end{equation*}

and for \(v \neq s\)

\begin{equation*} dp(v) = \min_{(u, v) \in E} dp(u) + w(u, v) \end{equation*}

The state graph is the same as the input graph and so this formulation will work if and only if the input graph is acyclic.

So what can we do if the input graph contains cycles, is it still possible to solve it with dynamic programming? YES. But we need to change the formulation so that the resulting state graph is acyclic.

Doing so requires some imagination and is problem dependent. However there are some general tricks.

Suppose that you have a formulation with states \(s \in S\). Imagine that you add a parameter \(i\) to the formulation and manage to make sure that each state \((s, i)\) only depends on states \((s, j)\) with \(j < i\). Then your new state graph is clearly acyclic since any path on it

\begin{equation*} (s_1, i_1), (s_2, i_2), \ldots, (s_k, i_k) \end{equation*}

must has have a strictly increasing \(i\) coordinates

\begin{equation*} i_1 < i_2 < \ldots < i_k \end{equation*}

This might seem a bit abstract so let's see a concrete example with the shortest path problem.

Define a new state \((v, i)\) with the following subproblem definition:

\(dp(v, i)\) equals the length of the shortest path from \(s\) to \(v\) that traverses at most \(i\) edges.

How to the subproblems relate to each other? To reach node \(i\) using at most \(i\) edges, we have two possibilities:

We reach some neighbor \(u\) of \(v\) using at most \(i - 1\) edges and then traverse edge \((u, v)\)
We reach \(v\) using at most \(i - 1\) edges.

Mathematically, this means that

\begin{equation*} dp(v, i) = \min \begin{cases} \min \left\{ dp(u, i - 1) + w(u, v) \mid (u, v) \in E \right\} \\ dp(v, i - 1) \end{cases} \end{equation*}

The base case is when \(i = 0\). In this case we only use paths with \(0\) edges the only node that is reachable from the source \(s\) is itself. If \(d(v, i)\) is not defined, that is, the path of at most \(i\) edges from \(s\) to \(v\) exists, we define \(d(v, i) = \infty\). In particular, it means that we initialize \(d(v, 0) = \infty\) for each \(v \neq s\).

With this formulation we can now solve the following problem:

Given a weighted graph \(G\) and a source \(s\), what is the shortest path from \(s\) to \(v\) using at most \(i\) edges?

Notice that with positive edge weights, any shortest path uses at most \(|V| - 1\) edges (such a shortest path cannot have cycles). This means that we only need to compute the answer for states until \(i = |V| - 1\). The answer to the shortest path problem from \(s\) to \(v\) will therefore be \(dp(v, |V| - 1)\).

What did we lose by extending the space state? We lost efficiency, now there are \(O(|V|^2)\) states.

It should be easy now to implement this ideas. Simply create a matrix to store the values of \(dp(v, i)\) and compute them in increasing order of \(i\) using the above relation.

Since for each \(i = 0, \ldots, |V| - 1\) we need to iterate over the graph, the total runtime will be \(O(|V| (|V| + |E|))\). This is equal to \(O(|V| |E|)\) for any connected graph.

Paste this command into your terminal:

The password to connect is

Alice is afraid of flying

Alice wants to travel from her home country \(A\) to her dream destination \(B\). There are several flights available connecting the cities in the world each with a certain price \(p\). She does not really like to fly, she particularly really hates the takeoff. Therefore, so she would like to go travel without having to fly more than \(k\) times.

Can you help her find the cheapest way to fly from \(A\) to \(B\) without flying more than \(k\) times?

Input

One line with four integers \(n\), \(m\), \(A\), \(B\) and \(k\) giving the number of cities, the number of flights connecting pairs of cities, her home city, her dream destination and the maximum number of flights that she can bear.
\(m\) lines each with with three integers \(a, b\) and \(p\) giving that she can fly betweens cities \(a\) and \(b\) at cost \(p\). Note that flights are bidirectional.

The cities are represented by numbers from 0 to \(n - 1\). You can assume that it is possible to travel (possibly indirectly) between any to pairs of cities.

Output

A single integer with the minimum cost for traveling from \(A\) to \(B\) with at most \(k\) flights.

If it is impossible for Alice to reach her destination in at most \(k\) flights, print impossible.

Constraints