All Tracks Algorithms Graphs Shortest Path Algorithms Problem

Routes
Tag(s):

Algorithms, Easy, Graph, Shortest path problem

Problem
Editorial
Analytics

A consultant earns an amount K per hour of his time. He has to fly from city A to city B spending the least cost. Every hour that he spends traveling or waiting in an airport for connecting flights, he is losing an amount K. Assume that layover time between connecting flights is always one hour. Given inputs as N - the number of cities, – the number of routes between cities (not all cities are necessarily connected), costs and time of flights between two cities for X routes (same in both directions), the source city number S  and the destination city number D , please output the most optimal route S->[any intermediate cities]->D, total time in hours T and total cost C (including opportunity cost of lost earnings).

 

Input format:

The first line contains K.

The second line contains N.

The third line contains X.

Next X lines contain X route quadruplets involving source city number, destination city number, flight time and flight cost

Next line contains S.

Next line contains D.

 

Output format:

Print the optimal route in the follow format:

S->[C1->C2->… ->Cy]->D T C

If there is no route possible or if any of the constraints is failing, print Error.

 

Constraints:

\(1 \le X \le \frac {N*(N-1)}2\)

\(1 \le K \le 1000\)

\(1 \le S, D \le N\)

SAMPLE INPUT
1000
4
5
1 2 1 2500
1 3 1 3000
1 4 2 7000
2 4 1 3000
3 4 1 2000
1
4
SAMPLE OUTPUT
1->3->4 3 8000
Explanation

.

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: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

ServiceNow

Challenge Name

ServiceNow Senior Developer Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?