Graph problem — Sprinklr coding test problem HELP!

Revision en2, by kassutta, 2020-08-14 07:21:33

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English kassutta 2020-08-14 07:23:31 63
en2 English kassutta 2020-08-14 07:21:33 2 This contest is Over for the kind information of my fellow downvoters, Thank you!
en1 English kassutta 2020-08-14 07:11:36 1164 Initial revision (published)