fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. //COPY THE BLACKBOX, there is no need to change anything in it.
  6. //Check the main function at bottom for USAGE
  7.  
  8. //****************BLACKBOX START*****************
  9. //START COPYING FROM HERE
  10.  
  11. typedef int ll;
  12.  
  13. class Hash {
  14.   public:
  15.   	static int hash(int x){
  16.   		return hash({0,0,x});
  17.   	}
  18.   	static int hash(tuple<int,int>x){
  19.   		return hash({0,get<0>(x),get<1>(x)});
  20.   	}
  21.   	static int hash(tuple<int,int,int>x){
  22.   		int k=get<0>(x),u=get<1>(x),v=get<2>(x);
  23.   		return k*1873*1873 + u*1873 + v;
  24.   	}
  25. };
  26.  
  27. class Graph {
  28.  
  29. 	bool is_directed;
  30.  
  31. 	public:
  32. 		vector<vector<pair<int,ll>>>adj;
  33.     int n,N=2000000;
  34.  
  35. 		Graph(int n_, bool is_directed_){
  36. 			n=n_; is_directed = is_directed_;
  37. 			adj.resize(N,vector<pair<int,ll>>());
  38. 		}
  39.  
  40. 		int hash(int u, int v){
  41. 			return Hash::hash({u,v});
  42. 		}
  43. 		int hash(int u, int v, int k){
  44. 			return Hash::hash({u,v,k});
  45. 		}
  46.  
  47. 		void add_edge(int uR, int vR, ll c=0){
  48. 		  int u=Hash::hash(uR), v=Hash::hash(vR);
  49. 		  add_edge_internal(u,v,c);
  50. 		}
  51. 		void add_edge(tuple<int,int> uR, tuple<int,int> vR, ll c=0){
  52. 		  int u=Hash::hash(uR), v=Hash::hash(vR);
  53. 		  add_edge_internal(u,v,c);
  54. 		}
  55. 			void add_edge(tuple<int,int,int> uR, tuple<int,int,int> vR, ll c=0){
  56. 		  int u=Hash::hash(uR), v=Hash::hash(vR);
  57. 		  add_edge_internal(u,v,c);
  58. 		}
  59.  
  60.  
  61. 	private :
  62.  
  63. 	  void add_edge_internal(int u, int v, ll c=0){
  64. 			add_edge_weighted_undirected(u,v,c);
  65. 			if(!is_directed)
  66. 				add_edge_weighted_undirected(v,u,c);
  67. 		}
  68. 		void add_edge_weighted_undirected(int u, int v, ll c) {
  69. 			pair<int,ll>p = make_pair(v,c);
  70. 			adj[u].push_back(p);
  71. 		}
  72.  
  73. };
  74.  
  75. class BFS { 
  76.     vector<ll>min_dist_from_source;
  77.     vector<bool> visited;
  78.     Graph *g;
  79.  
  80.     public:
  81.       BFS(Graph *g_) {
  82.           g = g_;
  83.           clear();
  84.       }
  85.  
  86. 	  	void clear() {
  87.   			min_dist_from_source.clear();
  88.   			min_dist_from_source.resize(g->N,-1);
  89.   			visited.clear();
  90.   			visited.resize(g->N, false);
  91.   		}
  92.  
  93.  
  94.       void run(int sourceR) {
  95.         int source = Hash::hash(sourceR);
  96.         run_internal(source);
  97.       }
  98.       void run(tuple<int,int> sourceR) {
  99.         int source = Hash::hash(sourceR);
  100.         run_internal(source);
  101.       }
  102.       void run(tuple<int,int,int> sourceR) {
  103.         int source = Hash::hash(sourceR);
  104.         run_internal(source);
  105.       }
  106.  
  107.  
  108.       int min_dist(int targetR){
  109.       	int target = Hash::hash(targetR);
  110.       	return min_dist_internal(target);
  111.       }
  112.       int min_dist(tuple<int,int> targetR){
  113.       	int target = Hash::hash(targetR);
  114.       	return min_dist_internal(target);
  115.       }
  116.       int min_dist(tuple<int,int,int> targetR){
  117.       	int target = Hash::hash(targetR);
  118.       	return min_dist_internal(target);
  119.       }
  120.  
  121.       bool is_visited(int targetR){
  122.       	int target = Hash::hash(targetR);
  123.       	return is_visited_internal(target);
  124.       }
  125.       bool is_visited(tuple<int,int> targetR){
  126.       	int target = Hash::hash(targetR);
  127.       	return is_visited_internal(target);
  128.       }
  129.       bool is_visited(tuple<int,int,int> targetR){
  130.       	int target = Hash::hash(targetR);
  131.       	return is_visited_internal(target);
  132.       }
  133.  
  134.   private:
  135.     void run_internal(int source) {
  136. 			queue<int> q;
  137. 			q.push(source);
  138.  
  139. 			visited[source] = true;
  140. 			min_dist_from_source[source] = 0;
  141.  
  142. 			while(!q.empty()) {
  143. 				int cur_node = q.front();
  144. 				for (unsigned int i = 0; i < (g->adj[cur_node]).size(); ++i) {
  145. 					int adj_node =  (g->adj[cur_node])[i].first;
  146. 					if (visited[adj_node] == false) {
  147. 						visited[adj_node] = true;
  148. 						min_dist_from_source[adj_node] = min_dist_from_source[cur_node] + 1;
  149. 						q.push(adj_node);
  150. 					}
  151. 				}
  152. 				q.pop();
  153. 			}
  154.  
  155. 			return;
  156.     }
  157.  
  158.     int min_dist_internal(int target){
  159.     	return min_dist_from_source[target];
  160.     }
  161.  
  162.     bool is_visited_internal(int target){
  163.     	return visited[target];
  164.     }
  165.  
  166. };
  167. //END COPYING HERE
  168. //********************BLACKBOX END******************
  169.  
  170. int main() {
  171.   int n,m; cin>>n>>m;
  172.  
  173.   Graph g(n,false);
  174.  
  175.   int x,y;
  176.   for(int i=0;i<m;i++){
  177.     cin>>x>>y;
  178.     g.add_edge(x,y);
  179.   }
  180.  
  181.   cin>>x>>y;
  182.  
  183.   BFS bfs(&g);
  184.   bfs.run(x);
  185.  
  186.   if(bfs.is_visited(y))
  187.     cout<<bfs.min_dist(y)<<'\n';
  188.   else
  189.     cout<<"0\n";
  190.  
  191.  
  192.  
  193.   return 0;
  194. }
  195.  
Success #stdin #stdout 0.03s 58124KB
comments (?)
stdin
copy 
5 5
1 3
2 3
1 2
3 5
4 5
1 4
stdout
copy 
3
https://ideone.com/YyepJd
language:
C++14 (gcc 8.3)
created:
1 year 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!