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.