Given is a graph of cities and cost of airways and roadways as edge weights between each pair of cities. We need to find min. cost to travel from source city to destination city given the constraint that I can travel through airways at max only once.
My approach so far: selecting each airways edge once then apply dijkstra to the remaining graph only on the roadways edges. Is there any way to improve this?