Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

mini4141's blog

By mini4141, history, 3 months ago, In English,

Hello, im thinking about this problem, but can't come up with a solution. (I dont know if this is classical problem or already exist in some online judge, please link in comment if it already exist)

You are given n flight plan, each flight plan has this following info (all are numbers)

  • source city

  • destination city

  • cost

  • flight time

  • arrival time

Print minimum cost to flight from A to B (A != B). It need 1 time break from arrival time to use other flight plan again

Example

Input:

1 3 // minimum cost from 1 to 3 ?

4 // how many flight plan? followed by 4 line here

1 2 5 0 5 // flight plan info: from, to, cost, flight_time, arrival_time

1 2 1 3 10

2 3 1 5 11

2 3 3 6 11

Output: 8 // using path at line 1, 4

Explanation: from 1 to 2 arrive at time 5, break for 1 unit of time, then start another flight plan from 2 to 3 at time 6 (can't use flight plan 3 because need 1 unit of time break)

how to solve?

 
 
 
 
  • Vote: I like it  
  • +2
  • Vote: I do not like it  

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you can do some sort of modified dijkstra. You will only ever have N + M nodes in the graph because you only need to store a distinct number of times for the amount of times that a plane can leave a station/node. Therefore it will be relatively quick.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    thank you, i think i can solve it now (with + M nodes and modified dijkstra choice)