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, ,

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?

•
• +2
•

 » 3 months ago, # |   0 Auto comment: topic has been updated by mini4141 (previous revision, new revision, compare).
 » 3 months ago, # |   0 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, # ^ |   +5 thank you, i think i can solve it now (with + M nodes and modified dijkstra choice)