sudddddd's blog

By sudddddd, history, 4 years ago, In English

How do we solve a problem in which arrival time and departure time of many flights are given (also source and destination of each flight are given) and we have to find the path between source and final destination which takes least time.

We also have to take care our waiting time for next flight(overall time should be minimised).

There are multiple flights possible from a destination.

X <= 500

N <= 4 * X * (X -1)

Where x is number of stations and N is total number of flights.

Time limit is 3s.

Eg.- Consider three stations (1,2,3), we have to go from 1 to 3.

flight 1 leaves station 1 at 10:30 and arrives at station 2 at 11:50.(time=80 min)

flight 2 leaves station 1 at 10:45 and arrives at station 2 at 12:15.(time=90 min)

flight 3 leaves station 2 at 12:30 and arrives at station 3 at 14:30.(time=120 min)

If we take flight 1 our total time spent = 80 + 40 (for waiting for flight 3) + 120 =240 min.

If we take flight 2 total time =90 + 15 + 120 = 225 min.

So finally we would take flight 2 and 3.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Bounds of the problem would be helpful!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sudddddd (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

If there is a flight between x and y and departure time < shortest distance to x, you won't be able to use that flight. If departure time > shortest distance to x you can just wait, so just run a modified dijkstra.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    But this does not guarantee that overall time will be minimum. Eg.-

    Consider three stations (1,2,3), we have to go from 1 to 3.

    flight 1 leaves station 1 at 10:30 and arrives at station 2 at 11:50.(time=80 min)

    flight 2 leaves station 1 at 10:45 and arrives at station 2 at 12:15.(time=90 min)

    flight 3 leaves station 2 at 12:30 and arrives at station 3 at 14:30.(time=120 min)

    If we take flight 1 our total time spent = 80 + 40 (for waiting for flight 3) + 120 =240 min.

    If we take flight 2 total time =90 + 15 + 120 = 225 min.

    So finally we would take flight 2 and 3.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What do you mean by shortest distance? Can you elaborate.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone is interested in shortest path problem in the so called temporal graphs (or time-varying graphs), this paper was a great read: Path Problems in Temporal Graphs. In particular, your problem is equivalent to the "fastest path" variant.