UPDATE: CONTEST IS OVER MANY DAYS AGO DOWNVOTERS SO PLEASE!
You are given 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 are using this wildcard while using the road, you do not need to pay tax associated to road. You are planning to visit one city this weekend, due to limited budget you want to estimate minimum possible cost from your 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.
Input Format: First line of input contains N,M and K following M lines contains 3 integer U V C , meaning there is a road between cities U and V with tax associated.
Output Format: Print N space separated integers in a single line, ith integer indicating the minimum cost of travelling from city 1 to i.
Sample Input 4 4 1 1 2 2 2 3 3 1 3 6 3 4 11
Sample Output 0 0 0 5
Auto comment: topic has been updated by kassutta (previous revision, new revision, compare).
Auto comment: topic has been updated by kassutta (previous revision, new revision, compare).
What are the constraints, bbruh?
constraints were not mentioned there , i was having this problem, so any solution that comes to ur mind u can share
Exactly the same Problem: https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/practice-problems/algorithm/shortest-path-revisited-9e1091ea/
Yes thank you very much now i can solve it with given constraints and refer to the editorial
Just curious, does using a dfs, with passing all the path weights/taxes in a priority queue will work?
The only shortcoming I can think of is I might use a lot of memory, which might cause MLE for large test cases.
yes this is a kind of brute force can work depends on constraints.
Using priority queue to store each value he has to pay and a normal bfs will work and then discarding initial k values from each if they exist.
ya kind of, Dijksta using priority queue will work with Dp.