MELE3 #modified dijikstra

Question kehna kya chahta hai :

Elevator from node A to node B, takes 5 sec per floor and oscillates between A and B. We have to travel from floor 1 to last floor (N). At any floor there can be multiple stops of elevators.

Key points: 

So visualise it as a graph. At any node, we can ride any elevator, but we have to wait till the elevator comes and stops there. There can we multiple ways to reach the top. To find the quickest, we use dijikstra. Now I wont go into details of dijikstra but we maintain a priority queue that has minimum time node at the top.

The information we need to store in the queue with each element is: (time taken till now, floor on which we are currently)

If we have used an elevator, it will be redundant in using it again so we mark the elevator when we use it.

If we are on floor X, the quickest path can be through any one of the elevators that stop on it. So add all the elevators to queue.

We have to wait for the elevator to stop at the floor. For that we use the current time taken and the  time it takes for the elevator to oscillate.

Code:

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define pii pair<int,int>
#define ppi pair<int,pair<int,int> >
#define mp make_pair
#define INF 1e8
#define M(x) memset(x,0,sizeof(x))
using namespace std;

int graph[1005][1005];
int n,k,check[1005][1005],a,b;

void dij() {
    priority_queue<pii,vector<pii>,greater<pii> > q;
    q.push(mp(0,1));
   
    while(!q.empty()){
        pii temp=q.top();
        q.pop();
        int time=temp.first,v=temp.second;
       
        if(v==n) {cout<<time<<endl; return;}
        REP(i,1,n){
            if(graph[v][i]&&!check[v][i]){
                check[v][i]=1;
                int vi=abs(v-i);
                if(graph[v][i]==1){
                    int mm=((10*(vi))-(time%((10*(vi)))))%((10*(vi)))+5*(vi);
        //            cout<<i<<" "<<time+mm<<endl;
                    q.push(mp(time+mm,i));
                }
                else{
                    int mm;
                    if(time>=5*(vi))
                    mm=((10*(vi))-((time-5*(vi))%((10*(vi)))))%((10*(vi)))+5*(vi);
                    else
                    mm=5*abs(v-i)-5*time;
        //            cout<<i<<" "<<time+mm<<endl;
                    q.push(mp(time+mm,i));
                }
            }
        }
    }
    cout<<-1<<endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    REP(i,0,k-1){
        cin>>a>>b;
        graph[a][b]=1;
        graph[b][a]=2;
    }
    dij();
}