May be it helps you to see more easily the way to attack the problem. The first that you could try it's find or understand the recursive relation behind Floyd-Warshall Algorithm. As the next function $f$.

$$ f(u,v,k) = \begin{cases} w_{u,v} & k = 0\\ \min\, (\ f(u,v, k-1),\ f(u,k,k-1) + f(k,v,k-1)) & \text{otherwise} \end{cases} $$

• $w_{u,v}$ it's the weight of edge from $u$ to $v$ in the direct graph $G$. $\infty$ if that edge doesn't exist.
• $f(u,v,k)$ is the weight of a shortest path from $u$ to $v$ if you consider the first $k$ vertices as intermediates.

To adapt the above function form for your problem, I'd sketched the essence of the problem in the next graph:

• 
• $m_i\in E_0$
• $l_i\in E_1$
• The curly curve is the shortest path considering the first $k-1$ vertices.
• You have a alternate path that consider the $k$ node when you see the pattern (normal-$k$-dashed) lines in the path, or with convention above: (dashed-$k$-normal) line or $(m_i, l_j)^*$ , $(l_i, m_j)^*$ pattern in general.

So the next step it's construct the recursive relation looking the connection between subproblems, and for that you could think for a moment that your function solve the problem for a small size of problem, or instances pattern (follow principle of optimality).

$$ f(u,v,k,i) = \begin{cases} w_{u,v,i} & k = 0\\ \min\, (\ f(u,v, k-1,i),\ f(u,k,k-1,~i) + f(k,v,k-1,i)) & \text{otherwise} \end{cases} $$

• $w_{u,v,i}$ is the weight for the edge in $E_i$ (Note that I change enumeration of $E$ for convenience). $\infty$ if that edge doesn't exist.
• $f(u,v,k,i)$ is the weight of a shortest path that ended up with a edge in $E_i$ that consider the first $k$ vertices as intermediates like the graph above.
• $~i = 0$ if $i = 1$ or $1$ if $i = 0$.

So, the weight of the shortest alternate path from $u$ to $v$ is $\bf{min(f(u,v,|V|,0), f(u,v,|V|,1))}$ where $|V|$ is the number of vertices.

Of course, after some work, you could notice that:

• It's possible delete parameter $k$
• you could implement iterative version or use a memorization technique.
• Other details, that I'm forgiving. It's late.

I'd wrote a python code/ and input test file if you can play with that. But, Here, it's not important.

May be it helps you to see more easily the way to attack the problem. The first that you could try it's find or understand the recursive relation behind Floyd-Warshall Algorithm. As the next function $f$.

$$ f(u,v,k) = \begin{cases} w_{u,v} & k = 0\\ \min\, (\ f(u,v, k-1),\ f(u,k,k-1) + f(k,v,k-1)) & \text{otherwise} \end{cases} $$

• $w_{u,v}$ it's the weight of edge from $u$ to $v$ in the direct graph $G$. $\infty$ if that edge doesn't exist.
• $f(u,v,k)$ is the weight of a shortest path from $u$ to $v$ if you consider the first $k$ vertices as intermediates.

To adapt the above function form for your problem, I'd sketched the essence of the problem in the next graph:

• 
• $m_i\in E_0$
• $l_i\in E_1$
• The curly curve is the shortest path considering the first $k-1$ vertices.
• You have a alternate path that consider the $k$ node when you see the pattern (normal-$k$-dashed) lines in the path, or with convention above: (dashed-$k$-normal) line or $(m_i, l_j)^*$ , $(l_i, m_j)^*$ pattern in general.

So the next step it's construct the recursive relation looking the connection between subproblems, and for that you could think for a moment that your function solve the problem for a small size of problem, or instances pattern (follow principle of optimality).

$$ f(u,v,k,i) = \begin{cases} w_{u,v,i} & k = 0\\ \min\, (\ f(u,v, k-1,i),\ f(u,k,k-1,~i) + f(k,v,k-1,i)) & \text{otherwise} \end{cases} $$

• $w_{u,v,i}$ is the weight for the edge in $E_i$ (Note that I change enumeration of $E$ for convenience). $\infty$ if that edge doesn't exist.
• $f(u,v,k,i)$ is the weight of a shortest path that ended up with a edge in $E_i$ that consider the first $k$ vertices as intermediates like the graph above.
• $~i = 0$ if $i = 1$ or $1$ if $i = 0$.

So, the weight of the shortest alternate path from $u$ to $v$ is $$\min \,(\, f(u, v, |V|, 0),\ f(u, v, |V|, 1) )$$ where $|V|$ is the number of vertices.

Of course, after some work, you could notice that:

• It's possible delete parameter $k$
• you could implement iterative version or use a memorization technique.
• Other details, that I'm forgiving. It's late.

I'd wrote a python code/ and input test file if you can play with that. But, Here, it's not important.