All Tracks Algorithms Graphs Shortest Path Algorithms Problem

Smart travel agent
Tag(s):

Algorithms, Easy, Graph, Shortest path problem

Problem
Editorial
Analytics

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

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

[Input]:
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.

[Output]:
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

SAMPLE INPUT
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
SAMPLE OUTPUT
1 2 4 7
5
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

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

JDA Software

Challenge Name

JDA Hackathon

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?