You are not logged in. Please login at www.codechef.com to post your questions!

×

trip planner problem

0
1

"what will be a best approach for solving this" The input is the set of flights between various cities. It is given as a file. Each line of the file contains "city1 city2 departure-time arrival-time flight-no. price" This means that there is a flight called "flight-no" (which is a string of the form XY012) from city1 to city2 which leaves city1 at time "departure-time" and arrives city2 at time "arrival-time". Further the price of this flight is "price" which is a poitive integer. All times are given as a string of 4 digits in the 24hr format e.g. 1135, 0245, 2210. Assume that all city names are integers between 1 and a number N (where N is the total number of cities).

Note that there could be multiple flights between two cities (at different times).

The query that you have to answer is: given two cities "A" and "B", times "t1", "t2", where t1 < t2, find the cheapest trip which leaves city "A" after time "t1" and arrives at city "B" before time "t2". A trip is a sequence of flights which starts at A after time t1 and ends at B before time t2. Further, the departure time from any transit (intermediate) city C is at least 30 mins after the arrival at C

asked 24 Apr '15, 00:10

rak007's gravatar image

0★rak007
11
accept rate: 0%

kindly specify the constraints of the possible input..this will give an insight to the expected efficiency of the solution..

(24 Apr '15, 02:42) gvaibhav217★

Answer is hidden as author is suspended. Click here to view.

answered 24 Apr '15, 12:38

bangga's gravatar image

0★bangga
(suspended)
accept rate: 0%

Will some one flag this as spam. I ran out of flags for today flgging this guys spams ( currently, he has 7 spams )

(24 Apr '15, 12:43) arun_as1★
Answer is hidden as author is suspended. Click here to view.

answered 24 Apr '15, 12:38

bangga's gravatar image

0★bangga
(suspended)
accept rate: 0%

Will some one flag this as spam. I ran out of flags for today flgging this guys spams ( currently, he has 7 spams )

(24 Apr '15, 12:44) arun_as1★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,664
×1,409
×374
×57

question asked: 24 Apr '15, 00:10

question was seen: 1,301 times

last updated: 24 Apr '15, 12:44