Reverse Edges : Dijkstra's Algorithm Implementation

You have been given a directed graph consisting of N nodes and M edges.Vertices are numbered from 1 to N.The problem is to find the minimum number of edges that are needed to be reversed to reach the destination node from vertex 1.

Input:

The first line of the input contains two space separated integers N and M, denoting number of vertices and the number of edges respectively.The next ith line of the next M lines consists of two space separated integers Xi and Yi, denoting an edge directed from Xi to Yi.The last line of the input consists of an integer D, denoting the destination vertex.

Constraints:

1<=N,M<=100000

1<=Xi,Yi<=N

There can be multiple edges connecting the same pair of vertices.

There can be self loops too.

Output:

In a single line, print the minimum number of edges that we need to revert.If there is no way of reaching vertex D from vertex 1, print -1.

Example:

Input:
7 7
1 2 
3 2
3 4
7 4
6 2
5 6
7 5

7

Output:
2

Algorithm:




We will apply Dijkstra's Algorithm(for single source shortest path) to solve the given problem.Let the weight of the provided edges be 0 and for each given edge ,add a reverse edge of it having weight 1 unit.Now, apply Dijkstra's Algorithm for finding the minimum weighted path(path with minimum edges reversed) from vertex 1, or vertex 1 as a source.





Solution:


/*
Reverse Edges


submitted by
Arjun Mishra
*/
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#define pp pair<int,int>
#define MAX 100001
#define INF 1000000000
//#define getchar_unlocked() getchar()
typedef long long LL;
using namespace std;
inline int read() //faster input for integer
{
 int n = 0;
 register char c = getchar_unlocked();//register is used due to its repeated use
 while (!('0' <= c && c <= '9'))
  {
    c = getchar_unlocked();
  }
  while ('0' <= c && c <= '9')
 {
   n = (n<<3) + (n<<1) +  c - '0';//equivalent to n = n*10 + c - 48;
   c = getchar_unlocked();
 }
 return n;
}
struct Prior
{
 int operator() ( const pair<int, int>& p1, const pair<int, int>& p2 )
    {
        return p1.second > p2.second;
    }
};
vector<pp> AdjList[MAX];
int dist[MAX],visited[MAX]={};
priority_queue<pp, vector<pp > , Prior > Queue;
//precomputation
void precompute()
{
 for(int i=0;i<MAX;i++)
 dist[i]=INF;//initially distance between vertex 1 and other vertices is infinity
}
int main()
{
 precompute();
 int N,M,D;
 N=read();
 M=read();
 while(M--)
 {
  int u,v;
  u=read();
  v=read();
        AdjList[u].push_back(pp(v,0));//given edge with weight 0
        AdjList[v].push_back(pp(u,1));//reverse edge with weight 1
 }
 D=read();
 //applying dijkstra
 int source=1;
    dist[source] = 0;
    Queue.push(pp(source,dist[source]));
    while(!Queue.empty())
    {
        int u,v,w;
 u = Queue.top().first;
        Queue.pop();
        int size = AdjList[u].size();
        for(int i = 0 ; i < size ; i++)
        {
            v = AdjList[u][i].first;
            w = AdjList[u][i].second;
            if(dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                Queue.push(pp(v,dist[v]));
            }
        }
    AdjList[u].clear();
    }
    if(dist[D]==INF)//no path from 1 to D
    printf("-1\n");
    else
    printf("%d\n",dist[D]);
    return 0;
}