This problem is easily solved if you:

- transform the input graph $G=(V,E)$ by either creating $n-1$ “levels”, where each level is a copy of $G$ and edges go from one level to the next; or
- consider the line graph $G’$ of $G$ instead (so that edges in $G$ become vertices in $G’$, and two vertices in $G’$ are adjacent if the corresponding edges in $G$ share an endpoint); or
- For each color $c in {red, blue}$, identify the maximal components $C$ of $G$ such that connectivity within $C$ is preserved using only edges of color $c$.

If you insist in using a dynamic programming algorithm, then the problem can be solved in $O(m)$ time using a Dijkstra-like algorithm.

Let’s start with some definitions:

Given a color $c in {red, blue}$, define a $c$-ending path as a simple path $P$ such that either 1) $P$ is empty, or 2) $P$ ends with an edge of color $c$.

Given a path $P$, let $ell(P)$ be the number of color changes encountered when traversing $P$.

We will say a path $P$ from $s$ to $v$ is a shortest $c$-ending path if there exist no other $c$-ending path $P’$ such that $ell(P’) < ell(P)$.

We will call $eta(v,c)$ the value of $ell(P)$, where $P$ is a shortest $c$-ending path from $s$ to $v$.

According to the above definitions $eta(s, red) = eta(s, blue) = 0$.

Moreover, the following suboptimality property holds:

**Claim:** Let $P$ be any shortest $c$-ending path from $s$ to $v$, let $u in P$.

The subpath $P(s:u)$ of $P$ going from $s$ to $u$ is a shortest $c’$-ending path where $c’$ is the color of the incoming edge in $u$ (if $u=s$ then $c’$ is any color).

**Proof:**

Assume that $u neq v$, otherwise the claim is trivial.

Let $c”$ be the color of the edge leaving $u$ in $P$.

Suppose towards a contradiction that $P(s:u)$ is not a shortest $c’$-ending path.

Let $P’$ be a shortest $c’$-ending path from $s$ to $u$, and notice that $Q = P’ circ P(u:v)$ is a (not necessarily simple) path from $s$ to $v$.

$Q$ ends with an edge of color $c$ and we have:

$$

ell(P) = ell(P(s:u)) + 1_{c’ neq c”} + ell(P(u:v))

> ell(P’) + 1_{c’ neq c”} + ell(P(u:v))

= ell(Q),

$$

contradicting the fact that $P$ is a shortest $c$-ending path. $square$

For each node $v$ we will maintain two upper bound $tilde{eta}(v, red)$ and $tilde{eta}(v, blue)$ on $eta(v, red)$ and $eta(v, blue)$, respectively. Initially $tilde{eta}(s, red)=tilde{eta}(s, blue)=eta(s, red) = eta(s, blue) = 0$ while, for $v neq s$, $tilde{eta}(s, red)=tilde{eta}(s, blue) = +infty$.

Finally, we will maintain a priority queue $Q$ in which keys are pairs $(v,c)$ where $v$ is an unmarked vertex and $c$ is a color, and the corresponding priority will be $tilde{eta}(v, c)$. Initially all pairs $(v,c)$ are in the queue.

The algorithm proceeds as follows: while $Q$ is not empty, extract $(u,c)$ from $Q$; for each edge $e=(u,v) in E$ let $c’$ be the color of $e$ and set $tilde{eta}(v, c) = min{tilde{eta}(v, c), tilde{eta}(u, c) + 1_{c neq c’} }$ (thus possibly updating the priority of $(v,c)$, if such a pair is in $Q$).

It is clear by construction that all values $tilde{eta}(v, c)$ are upper bounds to $eta(v,c)$ as claimed. We now prove that, when the pair $(v,c)$ is extracted from $Q$, $tilde{eta}(v, c)$ is also a lower bound to $eta(v,c)$, thus proving that $tilde{eta}(v, c) = eta(v,c)$.

**Claim:** When $i$-th pair $(v_i,c_i)$ is extracted from $Q$, $tilde{eta}(v, c) le eta(v,c)$.

**Proof**:

Let $i$ be the smallest value such that, when $(v_i, c_i)$ is extracted from $Q$ we have $tilde{eta}(v_i, c_i) > eta(v_i,c_i)$.

Since the values $tilde{eta}(v_i, c_i)$ never decrease during the execution of the algorithm and cannot become negative we know that $v_i neq s$.

Let $P$ be a shortest $c_i$-ending path from $s$ to $v_i$ and consider the last vertex $x$ such that the incoming edge in $x$ in $P$ has color $c_x$ (if $x=s$ let $c_x$ be any color) and $x=v_j$ and $c_x=c_j$ for some $j<i$ (notice such a vertex always exists since the above conditions are satisfied for $x=s$).

Let $y$ be the vertex following $x$ in $P$ and $c_y$ be the color of the incoming edge.

Since $(v_i, c_i)$ was extracted instead of $(y, c_y)$ we must have:

$$

tildeeta(v_i, c_i) le tildeeta(y, c_y)

$$

Moreover, since $(x, c_x)$ was already extracted from $q$ we have:

$$

tildeeta(y, c_y) le tildeeta(x, c_x) + 1_{c_x neq x_y} = eta(x, c_x) + 1_{c_x neq x_y}

$$

And, by suboptimality:

$$

eta(x, c_x) + 1_{c_x neq x_y} =

eta(y, c_y) le eta(v_i,c_i),

$$

which is a contradiction $square$.

The sought quantity is then $min{tildeeta(t,red), tildeeta(t,blue) }$.

Finally, notice that the the priority can only decrease in $Q$, that the priority of the extracted pairs is monotonically increasing, and that the only possible values of the priorities are ${0, 1, dots, n} cup { +infty }$. Therefore it is possible to implement a priority $Q$ that requires $O(n+m) = O(m)$ time to perform all the required $O(n)$ insertions and $O(m)$ priority updates.