Algorithm
Problem link- https://www.spoj.com/problems/MELE3/
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 immediately 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
Input: 10 4 1 5 5 10 5 7 7 10 Output: 45
Input: 10 3 1 5 3 5 3 10 Output: 105
Input: 20 5 1 7 7 20 4 7 4 10 10 20 Output: 150
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> ii;
typedef vector<vector<pair<int,ii> > > vviii;
#define se second
#define fi first
#define pb push_back
const int INF = 0x3f3f3f3f;
int k,n;
vviii neighbors;
vector<int> dist;
void dijkstras(){
priority_queue<ii,vector<ii>,greater<ii> > pq;
pq.push(ii(0,1));
dist[1] = 0;
while(!pq.empty()){
ii top = pq.top();
pq.pop();
int node = top.se;
int current_time = top.fi; // current time
for(int i = 0;i<(int)neighbors[node].size();++i){
int start_time = neighbors[node][i].se.fi; //start time for elevator
int trip_time = neighbors[node][i].se.se;
int n = neighbors[node][i].fi;
int wait_time;
if(start_time>=current_time){ // if start time is greater than current time that means we will have to wait
wait_time = start_time-current_time;
}
else{
// else if at current time the lift is not present we find the waiting time.
int temp = (current_time-start_time)%trip_time;
wait_time = temp==0 ? 0 : trip_time - temp;
}
if(dist[n]>current_time+wait_time+trip_time/2){ //time at which the lift reaches is current time + wait time + trip time /2
dist[n]=current_time+wait_time+trip_time/2;
pq.push(ii(dist[n],n));
}
}
}
}
int main(){
while(scanf("%d %d",&k,&n)>0){
neighbors = vviii(k+1,vector<pair<int,ii> > ());
int u,v;
dist = vector<int> (k+1,INF);
while(n--){
scanf("%d %d",&u,&v);
neighbors[u].pb(pair<int,ii>(v,ii(0,2*(v-u)))); // add starttime for the elevator along with trip time
neighbors[v].pb(pair<int,ii>(u,ii(v-u,2*(v-u))));
}
dijkstras();
printf("%d\n",dist[k]*5);
}
return 0;
}Input
1 5
5 10
5 7
7 10
Output
Demonstration
SPOJ Solution-MELE3 MELE3-Solution in C, C++, Java, Python