You are not logged in. Please login at www.codechef.com 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$.

INPUT FORMAT

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.

OUTPUT FORMAT

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

CONSTRAINTS

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

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

SAMPLE INPUT

4 4 1

1 2 2

2 3 3

1 3 6

3 4 11

SAMPLE OUTPUT

0 0 0 5

asked 12 Jan, 19:38

temp_typedef's gravatar image

2★temp_typedef
11
accept rate: 0%

edited 13 Jan, 10:35

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×2,169
×726
×505
×185
×127

question asked: 12 Jan, 19:38

question was seen: 143 times

last updated: 13 Jan, 10:35