# find all paths from source to destinations and then calculate the path with minimum cost

I am trying to solve one problem. Please refer complete problem statement before proceeding.

You are given a road network, with N cities and M bi-directional roads. Each road has some positive amount of tax associated to it,meaning if there is a road connecting cities A and B with tax C, you will need to pay C rupees to the government every time when you use this road.

but you have a wildcard which can be used at most K times and when you use wildcard while using a road, you do not need to pay tax associated with the road.

You are planning to visit one city this weekend, due to limited budged you want to estimate minimum passible cost from you home-city to every other city, so that you can choose the destination according to the budget, your home-city is a city numbered with 1.

For solving above problem I am Following this approach. Step 1) Calculate all the path between vertices u,v. Step 2) For a Path p=[i-j-k-l] do following

   for(int i=0;i<k;i++){
int weight=findEdgeWithMaxWeight(p);
cost of path p=cost of path-weight;
}


I am repeating this step2 for all the paths for u,v and at last I am choosing the path with minimum weight. As my answer.

Consider following diagram to visualize my approach.

But problem with above approach is that I am have to calulate all the path between u,v to get the answer. Is there any way to get the optimal path with out calculating all the paths?

Edit: Hope Problem is bit clearer now.

The distance array will be 2-dimensional array for which $$Dist[i][j]$$ is the shortest path from the source to the city $$i$$ using $$j$$ wildcards.
When processing a vertex $$i$$, for an incident edge $$e\{i, j\}$$ with cost $$c$$ we update as following:(for all values of k)
$$Dist[j][k] = min(Dist[j][k], Dist[i][k] + C)$$
$$Dist[j][k] = min(Dist[j][k], Dist[i][k-1])$$ The correctness follows from the fact that we are trying all placements of the wildcards and keeping the so-far-optimal.
The runtime is the usual Dijkstra runtime multiplied by the $$K$$ factor in the relaxation i.e. $$O((e+n\log(n))k)$$ using Fibonacci Heaps.