All Tracks Algorithms Graphs Shortest Path Algorithms Problem

The Parking Slot

Algorithms, Dijkstra, Graph Theory, Graphs, Medium, Shortest Path Algorithms, Shortest-path


There is a parking facility which is in the form of a graph having N nodes and M edges. The graph does not have self loops or multiple edges.
Each node represents a parking slot and has a capacity of vehicles it can hold. Each edge \((u,v)\) has a weight w representing we can reach from node u to node v incurring a cost of w units. All parking slots have a parking fee F per vehicle which is same for all slots. There are K identical vehicles entering the parking facility, each vehicle enumerated with a distinct number from 1 to K. The vehicles enter in their natural order, that is, vehicle number 1 enters, then vehicle number 2, then 3 and so on till vehicle number K.
For each vehicle, you have to print the minimum total cost that is incurred on the vehicle owner. Here, total cost includes cost of the path taken to reach the parking slot and parking fee of the slot.
It is guaranteed that you can reach any slot from any other slot.
All vehicles entering the parking facility enter from the parking slot 1.

Input Format:

The first line consists of three integers N, M and F, denoting number of nodes, number of edges and parking fee respectively.
The second line consists of N space separated integers denoting the parking capacity of each parking slot. This array is represented by C[].
Following M lines contain three space separated integers each: \(u, v\) and w, denoting we can reach from node u to node v incurring a cost of w units.
The last line of input contains an integer K.

Output Format:

Print K space separated integers denoting answer for each vehicle. \(i^{th}\) integer in the space separated integers denotes answer for \(i^{th}\) vehicle number.
If it is not possible to park a vehicle , print \(-1\) for that vehicle.

Input Constraints:

\(1 \le N,F \le 10^5\)
\(N-1 \le M \le min(N*(N-1)/2, 2 * 10^5)\)
\(1 \le C[i] \le 10^3\)
\(1 \le u,v \le N; u!=v\)
\(1 \le w \le 10^9\)
\(1 \le K \le 10^5\)

5 4 20
1 2 1 1 2
1 2 2
4 5 1
3 4 1
1 3 1
20 21 22 22 22

Vehicle number 1 is parked at parking slot 1 only. So, total cost= 0+20 = 20 (0 because vehicle at parked at slot 1 only). This parking slot is now full.
Vehicle number 2 is parked at parking slot 3. Total cost= 1 + 20= 21 (1 because it costs 1 unit to reach slot 3 from slot 1). This parking slot is now full.
Vehicle 3 is parked at slot 2. Total cost = 2 + 20= 22.
Vehicle 4 is parked at slot 2. Total cost = 2 + 20= 22. This parking slot is now full.
Vehicle 5 is parked at slot 4. Total cost = 2 + 20= 22. This parking slot is now full.

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


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

GAP Inc. Java Hiring Challenge

View All Notifications