Input: Let G be a directed graph where each edge has a cost and a letter label r or b
Problem: Find, for every i, j vertex pair. the length of the cheapest path from i to j where the edge labels along the path form the sequence rb or rbrb or rbrbrb etc. So that the path alternates between r and ending with b
We can design a supergraph H where the paths correspond to the legal traverssal of G, we can split the original graph into two subgraphs that copy the exact same node, but not edge such that
