fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int n, m, b, c;
  6.  
  7. struct boil{
  8. 	int mass = 0;
  9. 	int number = 0;
  10. 	vector<boil*> address;
  11. 	vector<int> distance;
  12. };
  13.  
  14. int empty = 0;
  15. int near_tube = 0;
  16. vector<int> visit;
  17. //Комментарии с тестовым выводом оставлены специально. При понимании кода может помочь некая визуализация, достаточно лишь убрать "//".
  18. int Min_way(boil* A, int i, int from){
  19. 	//cout<<from+1<<"->"<<A[i].number+1<<"-->";//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  20.  
  21.  
  22. 	if(A[i].mass>b){
  23. 		near_tube = A[i].number;
  24. 		return 0;
  25. 	}
  26.  
  27. 	int min = 0;
  28.  
  29. 	bool t = 0;
  30. 	for(int j = 0; j < A[i].distance.size(); j++){
  31. 		bool t2 = true, t1 = true;
  32. 		for(int u = 0; u < visit.size(); u++){
  33. 			if(visit[u] == A[i].address[j] -> number) t2 = false;
  34. 			if(visit[u] == A[i].address[min]->number) t1 = false;
  35. 		}
  36. 		if(A[i].address[j]->number == empty || A[i].address[j]->number == from) t2 = false;
  37. 		if(A[i].address[min]->number == empty ||  A[i].address[min]->number == from) t1 = false;
  38.  
  39. 		if(A[i].distance[min] >= A[i].distance[j] && t2 || !t1 && t2){
  40. 			min = j;
  41. 			t = 1;
  42. 		}
  43. 	}
  44.  
  45. 	if(t == 0){
  46. 		if(A[i].distance.size() == 1){
  47. 			if(A[i].address[0]->mass > b){
  48. 				near_tube = A[i].address[0]->number;
  49. 				return A[i].distance[0];
  50. 			}
  51. 			else{
  52. 				return -1;
  53. 			}
  54. 		}
  55. 		else return -1;
  56. 	}
  57. 	else if(A[i].address[min]->mass == b){
  58. 		visit.push_back(A[i].number);
  59.  
  60. 		bool t1 = true;
  61. 		long long min2 = -1;
  62.  
  63. 		for(int k = 0; k < visit.size() && t1; k++){
  64. 			if(visit[k] == A[i].address[min]->number) t1 = false;
  65. 		}
  66. 		if(A[i].address[min]->number == from) t1 = false;
  67.  
  68. 		if(t1)	min2 = Min_way(A, A[i].address[min]->number, A[i].number);
  69. 		if(min2 >= 0) min2 += A[i].distance[min];
  70.  
  71. 	//	cout<<"("<<min2<<")";//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  72.  
  73. 		int n1 = near_tube;
  74.  
  75. 		for(int j = 0; j < A[i].distance.size(); j++){
  76. 			if(j != min && A[i].address[j]->mass >= b && A[i].address[j]->number != from){
  77. 				visit.push_back(A[i].number);
  78. 				long long a = 0;
  79. 				bool t3 = true;
  80. 				for(int k = 0; k < visit.size() && t3; k++){
  81. 					if(visit[k] == A[i].address[j]->number)t3 = false;
  82. 				}
  83.  
  84. 				if(A[i].address[j]->number == A[empty].number)t3 = false;
  85.  
  86.  
  87. 				if(t1 && t3){
  88. 					a = Min_way(A, A[i].address[j]->number, A[i].number);
  89. 				}
  90. 				else return -1;
  91. 				if( a>= 0) a += A[i].distance[j];
  92.  
  93. 			//	cout<<"("<<a<<")";//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  94.  
  95. 				if(a >= 0 && min2 >= a && A[near_tube].mass > b || min2 < 0){
  96. 					min2 = a;
  97. 					n1 = near_tube;
  98. 				}
  99. 				visit.clear();
  100. 			}
  101. 		}
  102. 		near_tube = n1;
  103. 		return min2;
  104. 	}
  105. 	else if(A[i].address[min]->mass < b){
  106. 		return -1;
  107. 	}
  108. 	else{
  109. 		near_tube = A[i].address[min]->number;
  110. 		return A[i].distance[min];
  111. 	}
  112. }
  113.  
  114. int main() {
  115. 	cin >> n >> m >> b >> c;
  116. 	boil A[n];
  117. 	for(int i = 0; i < n; i++){
  118. 		int a;
  119. 		cin>>a;
  120. 		A[i].mass = a;
  121. 		A[i].number = i;
  122. 		if(A[empty].mass > a) empty = i;
  123. 	}
  124.  
  125. 	int d, k, g;
  126. 	while(cin >> d >> k >> g){
  127. 			A[d-1].address.push_back(&A[k-1]);
  128. 			A[k-1].address.push_back(&A[d-1]);
  129. 			A[k-1].distance.push_back(g);
  130. 			A[d-1].distance.push_back(g);
  131. 	}
  132.  
  133. 	unsigned long long s = 0;
  134. 	while(A[empty].mass < b){
  135. 	/*	for(int i=0; i<n;i++){//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  136. 			cout<<A[i].mass<<" ";
  137. 		}cout<<endl;*/
  138.  
  139. 		unsigned long long a = Min_way(A, A[empty].number, A[empty].number);
  140. 		if(A[near_tube].mass - b + A[empty].mass < b){
  141. 			A[empty].mass += A[near_tube].mass - b;
  142. 			s += a * (A[near_tube].mass - b);
  143. 			A[near_tube].mass = b;
  144. 		}
  145. 		else{
  146. 			int tmp = b - A[empty].mass;
  147. 			A[near_tube].mass -= tmp;
  148. 			A[empty].mass = b;
  149. 			s += a * tmp;
  150. 		}
  151. 		//cout<<"   : "<<a<<" "<<A[empty].mass<<" "<<near_tube<<endl<<endl;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  152. 	}
  153.  
  154. 	cout<<s * c;
  155. 	return 0;
  156. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
5   5   4   6 
5  4  8  1  6
1  2  3
2  3  5
2  4  2
3  4  6
3  5  4
stdout
copy 
102
https://ideone.com/FmHYs0
Топливо
language:
C++14 (gcc 8.3)
created:
5 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!