fork(2) download
copy 
  1. // 0-1  bfs
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5. using namespace std;
  6. typedef long long ll;
  7. typedef pair<int,int> pairs;
  8.  
  9. vector<pairs> vec[100001];         //  vector representing single directed edges
  10.  
  11. int nodes,edges;
  12. int dis[100001];
  13.  
  14. void frak(){
  15. 	for(int i = 0;i<=nodes;i++){
  16. 		dis[i] = INT_MAX;              // initialising all distances from node 1 
  17. 	}
  18. }
  19.  
  20. int main(){
  21.  
  22. 	scanf("%d%d",&nodes,&edges);         
  23. 	frak();                               
  24. 	int a,b;
  25. 	for(int i = 0;i<edges;i++){
  26. 		scanf("%d%d",&a,&b);
  27. 		vec[a].push_back(make_pair(0,b));          // the direct edge given  has weight 0
  28. 		vec[b].push_back(make_pair(1,a));          // the extra edge (reverse) is marked as weight 1
  29. 	}
  30.  
  31. 	deque<int> q;                                // deque(double ended queue) initialsed
  32. 	q.push_back(1);                             // insert the node 1 in the deque
  33. 	dis[1] = 0;
  34.  
  35. 	while(!q.empty()){
  36. 		int no = q.front();
  37.  
  38. 		q.pop_front();
  39. 		if(no==nodes)                            // if the node at front of deque is nodes so break
  40. 		break;                                          
  41. 		for(int i = 0;i<vec[no].size();i++){      // scan the adjacency list connected to that element(no)
  42.  
  43. 			int el=  vec[no][i].second;
  44. 			int w =  vec[no][i].first;
  45.  
  46. 			if(dis[el]>dis[no]+w){              // condition same as dijkstra's
  47. 				dis[el] = dis[no]+w;              // update the distance of the connected node(el)
  48.  
  49. 				if(w==1){               // if we have to go through a reverse edge then add it to the back of the deque(it will be accessed late than edges having 0 weight
  50.  
  51. 					q.push_back(el);                 
  52. 			}
  53. 				else{                    //  if there is a direct edge then add that node to front of dequeue as it will be accessed first 
  54.  
  55. 				q.push_front(el);
  56. 			}
  57. 			}	
  58. 		}	
  59. 	}
  60. 	if(dis[nodes]==INT_MAX){
  61. 		cout<<"-1"<<endl;
  62. 	}
  63. 	else{
  64. 		cout<<dis[nodes]<<endl;
  65. 	}
  66.  
  67. }
Success #stdin #stdout 0s 5028KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/UOIv6U
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!