You are not logged in. Please login at to post your questions!


Weekend Planning

This question was asked in Sprinklr hiring challenge.

You are given a road network with $N$ cities and $M$ bidirectional 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 need to pay $C$ rupees to the government every time you use this road.

But you have a wildcard which can be used at most $K$ times and when you use this wildcard while using using this road, you do not need to pay tax associated with that road. You are planning to visit one city this weekend, due to the 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 your budget. Your home city is a city numbered $1$.


The first line of the input contains $N$, $M$, and $K$ following $M$ lines containing $3$ integers $U$, $V$ and $C$, meaning there is a road between cities $U$ and $V$ with tax $C$ associated.


Print $N$ space separated integers in a single line, ith integer indicating the minimum cost of travelling from city $1$ to $j$


$1$ <= $N$,$M$ <= $5 * 10^5$

$0$ <= $ K$ <= $15$


4 4 1

1 2 2

2 3 3

1 3 6

3 4 11


0 0 0 5

asked 12 Jan, 19:38

temp_typedef's gravatar image

accept rate: 0%

edited 13 Jan, 10:35

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 12 Jan, 19:38

question was seen: 143 times

last updated: 13 Jan, 10:35