fork(4) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct node{
  5. 	int value;
  6. 	node * next;
  7. 	node(int v, node * n = NULL){
  8. 		value = v;
  9. 		next = n;
  10. 	}
  11. };
  12.  
  13. struct queue{ // Структура очередь
  14. 	node * start;
  15. 	node * finish;
  16. 	int len = 0;
  17. 	queue(node * s = NULL, node * f = NULL){
  18. 		start = s;
  19. 		finish = f;
  20. 	}
  21. 	string push(int n){
  22. 		if(len == 0){
  23. 			node * new_node = new node(n,finish);
  24. 			start = new_node;
  25. 			finish = new_node;
  26. 		}else{
  27. 			node * new_node = new node(n,NULL);
  28. 			start -> next = new_node;
  29. 			start = new_node;
  30. 		}
  31. 		len++;
  32. 		return "ok";
  33. 	}
  34. 	int pop(){
  35. 		int v = finish -> value;
  36. 		finish = finish -> next;
  37. 		len--;
  38. 		return v;
  39. 	}
  40. 	int front(){
  41. 		return finish -> value;
  42. 	}
  43. 	int size(){
  44. 		return len;
  45. 	}
  46. };
  47.  
  48. int main() {
  49. 	int n, s, f;
  50. 	cin >> n >> s >> f;
  51. 	int graph[n][n];
  52. 	int dist[n]; // Массив расстояний от начальной до i-ой вершины
  53. 	bool used[n];
  54. 	for(int i = 0; i < n; i++){
  55. 		for(int j = 0; j < n; j++){
  56. 			cin >> graph[i][j];
  57. 		}
  58. 	}
  59. 	for(int i = 0; i < n; i++){
  60. 		dist[i] = 0;
  61. 		used[i] = false;
  62. 	}
  63. 	queue vertex; // Очередь вершин
  64. 	vertex.push(s-1);
  65. 	used[s-1] = true;
  66. 	while(vertex.size() != 0){
  67. 		int v = vertex.front();
  68. 		for(int i = 0; i < n; i++){
  69. 			if(graph[v][i] == 1 && used[i] == false){
  70. 				vertex.push(i);
  71. 				dist[i] = dist[v] + 1; 
  72. 				used[i] = true; // i-ая вершина пройдена и не будет корректироваться позже
  73. 			}
  74. 		}
  75. 		used[v] = true;
  76. 		vertex.pop();
  77. 	}
  78. 	cout << dist[f-1];
  79. 	return 0;
  80. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
5 1 4
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
stdout
copy 
2
https://ideone.com/dbjloE
Поиск в ширину
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!