MELE3  MELE3
English  Vietnamese 
Solitaire has N elevators. Each elevator are connecting exactly two floors and it does not stop on the floors between that two floors The speed of all the elevators are the same, 5 seconds to pass one floor.
On the beginning, each elevator is in its lower position and they are starting cruising to the upper floor. After some elevator come to its upper position, it immediatly starts to go back to its lower position, and so on...
Mirko is on the first (the lowest) floor and he wants as quick as possible come to the top of the solitaire. He can change elevators only on the floors that are common to both elevators, and if the other elevator is in that moment on that floor, that change does not take any time.
Write a program that will calculate minimal time in which Mirko can get to the top of the solitaire.
Input
In the first line of the input file there are two integers K and N, separated with space, number of floors in solitaire and number of elevators, 2 ≤ K ≤ 1000, 1 ≤ N ≤ 50000.
In each of the next N lines there are description of one elevator, two integers A and B, separated with space, 1 ≤ A < B ≤ K, means that elevator is travelling between floors A and B.
There are no two different elevators that travels between same floors.
Note: input data will guarantee that solution will always exists.
Output
In the only line of output file write minimal time (in seconds) from the text above.
Sample
liftovi.in 10 4 1 5 5 10 5 7 7 10 liftovi.out 45 liftovi.in 10 3 1 5 3 5 3 10 liftovi.out 105 liftovi.in 20 5 1 7 7 20 4 7 4 10 10 20 liftovi.out 150
hide comments
manishjoshi394:
20181210 09:31:59
Just create a function that will calculate weights of the edges depending on the time already elapsed. Simple dijkstra. 

sherlock11:
20180525 06:49:10
toughest part of question is to understand the question..........after reaching to a floor he can wait on that floor,the elevator don't need to be synchronous at the time for mirko to change the elevator.......this misunderstanding costed me 3 days and and raised question on my existence...finally i have answers for all the question.......by the way dijkstra with function to calculate wait time and there u go AC:) Last edit: 20180525 06:49:59 

badry atef:
20160603 15:49:29
normal dijkstra's algorithm with binary search to calculate waiting time got it ACC :D 

xamitksx:
20160408 19:27:13
NO STL is required . . variant of BFS ... 

marky:
20160302 18:33:22
How to calculate wait time for next lift? 

Russo:
20151109 00:40:26
DO NOT read/write from/to the files indicated. Just ignore those lines of the input and read from stdin and write to stdout. 

Ankur Singh:
20150622 08:02:56
can he change the elevator even when the elevator does not have a stoppage(begin / end) point. Like if one elevator goes from 1  5, other 3  5, can he change at floor 4 ? 

rush:
20150319 18:42:59
Nice variation of a classical algorithm. 

Amitayush Thakur:
20140902 18:05:32
My 100th submission on SPOJ :) 

Ninjaflyte:
20100617 15:48:00
@~!(*(@*!@^& : I am completely sure that my program is correct, yet its getting WA. Can you check what's wrong?

Added by:  ~!(*(@*!@^& 
Date:  20090408 
Time limit:  0.211s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  COI 03 