Find shortest path that goes through at least 5 red edges
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.