fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <deque>  
  4. using namespace std;
  5.  
  6. struct vertax{
  7. 	int vert, index, father; bool visited;
  8. 	vertax(int a){vert = a; index = 10001; father = a;visited = false;}
  9. 	vertax(int a, int b){
  10. 		vert = a;
  11. 		father = b;
  12. 		index = 10001;visited = false;
  13. 	}
  14. 	vertax(int a, int b, int x){
  15. 		vert = a;
  16. 		father = b;
  17. 		index = x;visited = false;
  18. 	}
  19. 	vector<vertax> follow;
  20. 	~vertax(){}
  21. };
  22.  
  23. struct graph{
  24. 	vector<vertax> v; // list of vertax
  25. 	int count;
  26. 	graph(){};
  27. 	graph(int n){
  28. 		count = n;
  29. 	}
  30. 	void get(){
  31. 		for(int i = 1; i <= count; i++){
  32. 			vertax v(i);
  33. 			for(int j = 1; j <= count; j++){
  34. 				int x;
  35. 				cin >> x;
  36. 				if(x != 0){
  37. 					vertax temp(j, i, x);
  38. 					v.follow.push_back(temp);
  39. 				}
  40. 			}
  41. 			graph::v.push_back(v);
  42. 		}
  43. 	}
  44. 	void write(){
  45. 		for(int i = 0; i < count; i++){
  46. 			cout << v[i].index << ":";
  47. 			for(int j = 0; j < v[i].follow.size(); j++){
  48. 				cout << v[i].follow[j].vert << " ";
  49. 			}
  50. 			cout << endl;
  51. 		}
  52. 	}
  53. 	void way(vertax& x){
  54. 		deque<vertax> list;
  55. 		x.index = 0;
  56. 		x.visited = true;
  57. 		list.push_front(x);
  58. 		while(!list.empty()){
  59. 			vertax& y = list[0];
  60. 			for(int i = 0; i < y.follow.size();i++){
  61. 				v[y.follow[i].vert -1].visited = true;
  62. 				if(v[y.follow[i].vert-1].index > y.index+y.follow[i].index){
  63. 					v[y.follow[i].vert-1].index = y.index+y.follow[i].index;
  64. 					if(v[y.follow[i].vert-1].index > -102){
  65. 						list.push_back(v[y.follow[i].vert-1]);
  66. 					}
  67. 				}
  68. 			}
  69. 			list.pop_front();
  70. 		}
  71. 	}
  72. 	void def(){
  73. 		for(int i = 0; i < v.size(); i++){
  74. 			v[i].index = 10001;
  75. 			v[i].visited = false;
  76. 		}
  77. 	}
  78. 	void task1(){
  79. 		for(int i = 0; i < v.size(); i++){
  80. 			way(v[i]);
  81. 			for(int j = 0; j < v.size()-1; j++){
  82. 				if(!v[j].visited){
  83. 					cout << 0 << " ";
  84. 				}else if(v[j].index < -50){
  85. 					cout << 2 << " ";
  86. 				}else{
  87. 					cout << 1 << " ";
  88. 				}
  89. 			}
  90. 			if(!v[v.size()-1].visited){
  91. 					cout << 0 ;
  92. 				}else if(v[v.size()-1].index < -50){
  93. 					cout << 2 ;
  94. 				}else{
  95. 					cout << 1 ;
  96. 				}
  97. 			def();
  98. 			cout << endl;
  99. 		}
  100. 	}
  101. 	void task2(){
  102. 		for(int i = 0; i < v.size(); i++){
  103. 			way(v[i]);
  104. 			for(int j = 0; j < v.size()-1; j++){
  105. 				if(!v[j].visited){
  106. 					cout << 0 << " ";
  107. 				}else{
  108. 					cout << v[j].index << " ";
  109. 				}
  110. 			}
  111. 			if(!v[v.size()-1].visited){
  112. 					cout << 0 ;
  113. 				}else{
  114. 					cout << v[v.size()-1].index;
  115. 				}
  116. 			def();
  117. 			cout << endl;
  118. 		}
  119. 	}
  120. };
  121.  
  122.  
  123. int main() {
  124. 	ios::sync_with_stdio(false);
  125. 	int n;
  126. 	cin >> n;
  127. 	graph dog(n);
  128. 	dog.get();
  129. 	dog.task2();
  130. 	return 0;
  131. }
Success #stdin #stdout 0s 3304KB
comments (?)
stdin
copy 
4
0 5 9 100
100 0 2 8
100 100 0 7
4 100 100 0
stdout
copy 
0 5 7 13
12 0 2 8
11 16 0 7
4 9 11 0
https://ideone.com/uEdPzG
Флойд
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!