All Tracks Algorithms Graphs Shortest Path Algorithms Problem

Byteland Trip
Tag(s):

Algorithms, Binary Search, Floyd Warshall, Medium

Problem
Editorial
Analytics

Chintu is a member of the Lolympics committee and is assigned the task of dropping the players from the one stadium to another. There are total N stadiums in Byteland. There is at least one path between any two stadiums. Each stadium has a Dominos outlet near it. Chintu loves pizza and will not drive the bus until and unless he gets one when he's hungry. A trip from one stadium to another can be completed by buying atmost X pizzas for Chintu. He eats pizza at the beginning of each trip which is also counted as one of the X pizzas. Calculate the total minimum distance that Chintu can cover after eating a single pizza i.e. the distance after which Chintu gets hungry and throws tantrums.

Chintu can buy at most one pizza from one stadium.

Input:
The first line consists of N, X and M denoting the number of stadiums, maximum number of times Chintu can buy pizzas and the number of paths between the stadiums.
The next M lines consists of u,v and w denoting that there is a path from stadium u to stadium v of length w.

Output:
A single integer which is the desired distance.

Constraints:
1 <= N <= 102
1 <= X <= N
N-1 <= M <= 105
1 <= u,v <= N
1 <= w <= 109

SAMPLE INPUT
4 3 4
1 2 10
1 4 40
2 3 20
3 4 30
SAMPLE OUTPUT
30
Explanation

In the sample test case, Chintu can visit any stadium from another stadium after eating atmost 3 pizzas if the minimum distance he can cover after eating a single pizza is greater than or equal to 30.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

October Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications