All Tracks Algorithms Graphs Shortest Path Algorithms Problem

Smart travel agent

Algorithms, Easy, Graph, Shortest path problem


Our smart travel agent, Mr. X's current assignment is to show a group of tourists a distant city. As in all countries, certain pairs of cities are connected by two-way roads. Each pair of neighboring cities has a bus service that runs only between those two cities and uses the road that directly connects them. Each bus service has a particular limit on the maximum number of passengers it can carry. Mr. X has a map showing the cities and the roads connecting them, as well as the service limit for each bus service.

It is not always possible for him to take all tourists to the destination city in a single trip. For example, consider the following road map of seven cities, where the edges represent roads and the number written on each edge indicates the passenger limit of the associated bus service.

In the diagram below, It will take at least five trips for Mr. X. to take 99 tourists from city 1 to city 7, since he has to ride the bus with each group. The best route to take is 1 - 2 - 4 - 7.

enter image description here

What is the best way for Mr. X to take all tourists to the destination city in the minimum number of trips?

The first line will contain two integers: N (N ≤ 100) and R, representing the number of cities and the number of road segments, respectively. Each of the next R lines will contain three integers (C1, C2, and P) where C1 and C2 are the city numbers and P (P > 1) is the maximum number of passengers that can be carried by the bus service between the two cities. City numbers are positive integers ranging from 1 to N. The (R+1)th line will contain three integers (S, D, and T) representing, respectively, the starting city, the destination city, and the number of tourists to be guided.

The output should contain 2 lines - the first line giving the route taken and the second line giving the minimum number of trips

[Note]: If multiple solutions exist . Print lexicographically-smallest path .
Agent is also travelling in the same path so he has to be counted while travelling in that path for each trip.

*Problem provided by JDA

7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99
1 2 4 7
Time Limit: 5.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

JDA Software

Challenge Name

JDA Hackathon

View All Notifications