Find shortest path that goes through at least 5 red edges Let $G=(V,E)$ be a directed graph, $\omega : E \rightarrow R$ a weight function, and $s,t \in V$ a pair of different nodes. It's given that $G$ doesn't have a negative cycle. Moreover, 10 of its edges are colored in red (let's say that the rest are colored in blue).

I want to find an efficient algorithm that find the shortest path between $s$ and $t$ that goes through at least 5 different red edges. 

Notice that going more than once through the same red edge is still considered as going through 1 red edge in the path.

One idea that I had was creating a graph $G'$ that will have a copy of every node for every possible set of red edges in $G$. That means that if we go through some red edge $e$, then the path will "move" to a variation of $G$ where $e$ is colored in blue and all the rest is the same.

However in this solution I will have to copy each node and each edge around 400 times. This will result in the same complexity asymptotically, but with such a big constant it seems really not efficient.

Another idea, was to somehow build the new graphs "on the run" of Bellman-Ford algorithm, but I don't really know how to do it.

I'll appreciate some help.
What about reducing the problem first ?

UPDATED with more details :


Build 2 node subsets:


Vs contains s and the 10 reached nodes of the red edges (called a1, a2, ..., a10 hereafter). This is a 11 nodes set.
Vt contains t and the 10 sources nodes of the red edges (called b1, b2, ..., b10 hereafter). This is another 11 nodes set.

Build a distance matrix M from Vs to Vt (11x11)
Do 11 Dijksta explorations, one starting from any node of Vs to reach all nodes of Vt. So you get 11 shortest distances to report in the matrix M.
The diagonal terms are irrelevant (s->t or ak->bk).
For each row of M, add wi (the weight of the red edge) to all elements (0 for s row). This is the price of crossing the red edge.
Build an new graph G' with 11 nodes. node N0 for s&amp;t and nodes Nk for each red edge (ak &amp; bk). Then create all edges using matrix entry:
w(Ni -> Nj) = M[i][j].
Now your initial problem is equivalent to find a loop of 6 nodes containing N0 in G'.
Use any method to test all combinatoric for instance Apass.Jack one. This step in NP complete.