fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. //Рекомендация: чтение лучше начать с функции "main"
  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){//Если котёл в векторе адресов один, то 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.  
  61. 		bool t1=true;
  62. 		long long min2=-1;//Собственно, путь уже от этого котла, до ближайшего с топливом
  63.  
  64. 		for(int k=0; k<visit.size() && t1; k++){//Проверка, посещали ли
  65. 			if(visit[k]==A[i].address[min]->number)t1=false;
  66. 		}
  67. 		if(A[i].address[min]->number==from)t1=false;
  68.  
  69. 		if(t1)	min2=Min_way(A,A[i].address[min]->number,A[i].number);//Вызов самой фунции
  70. 		if(min2>=0)min2+=A[i].distance[min];//Если ветка не тупиковая (min2!=-1), то добавляем расстояние до данного котла (от котла для которого первоначально вызывалась фунцкия)
  71.  
  72. 	//	cout<<"("<<min2<<")";//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  73.  
  74. 		int n1=near_tube;//Запоминает значение near_tube, так как сама near_tube изменяется с каждым вызовом функции, и не всегда следующее значение правильное
  75.  
  76. 		for(int j=0; j<A[i].distance.size(); j++){//Перебераем все варианты 
  77. 			if(j!=min && A[i].address[j]->mass>=b && A[i].address[j]->number!=from){//Эти случаи уже рассматривали
  78. 				visit.push_back(A[i].number);//При вызове min2 фунция могла пройти и этот момент и дойти до обнуления visit, поэтому нужно отметить посещение ещё раз. 
  79. 				long long a=0;//Значение от рассматриваемой трубы
  80. 				bool t3=true;
  81. 				for(int k=0; k<visit.size() && t3; k++){//Проверка на посещение
  82. 					if(visit[k]==A[i].address[j]->number)t3=false;
  83. 				}
  84.  
  85. 				if(A[i].address[j]->number==A[empty].number)t3=false;
  86.  
  87.  
  88. 				if(t1 && t3){//Если не были, проеряем
  89. 					a=Min_way(A,A[i].address[j]->number,A[i].number);
  90. 				}
  91. 				else return-1;
  92. 				if(a>=0)a+=A[i].distance[j];//Не тупиковая ветка- добавляем расстояние
  93.  
  94. 			//	cout<<"("<<a<<")";//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  95.  
  96. 				if(a>=0 && min2>=a && A[near_tube].mass>b ||min2<0){//Нахождение, собственно, самого близкого из котлов, где есть топливо. Тупиковые пропускаются
  97. 				//Если минимум сам не ведёт к подходящему котлу, то подходят любые другие пути, которые ведут
  98. 					min2=a;
  99. 					n1=near_tube;
  100. 				}
  101. 				visit.clear();// обнуляем вектор для следующего витка цикла
  102. 			}
  103. 		}
  104. 		near_tube=n1;//возвращаем нужное значение
  105. 		return min2;//возвращаем значение функции
  106. 	}
  107. 	else if(A[i].address[min]->mass<b){
  108. 		return -1;
  109. 	}
  110. 	else{
  111. 		near_tube= A[i].address[min]->number;
  112. 		return A[i].distance[min];
  113. 	}
  114. }
  115.  
  116. int main() {//Ввод данных
  117. 	cin>>n>>m>>b>>c;
  118. 	boil A[n];
  119. 	for(int i=0; i<n; i++){
  120. 		int a;
  121. 		cin>>a;
  122. 		A[i].mass=a;
  123. 		A[i].number=i;
  124. 		if(A[empty].mass>a)empty=i;
  125. 	}
  126.  
  127. 	int d,k,g;
  128. 	while(cin>>d>>k>>g){//Да, возможно тут было бы логичнее "for", но один тест упорно не хотел проходиться с ним, так что пришлось оставить "while"
  129. 			A[d-1].address.push_back(&A[k-1]);//см. структуру "boil"
  130. 			A[k-1].address.push_back(&A[d-1]);
  131. 			A[k-1].distance.push_back(g);
  132. 			A[d-1].distance.push_back(g);
  133. 	}//Таким образом порядковый номер близлежащего котла в "address" будет совпадать с расстоянием между этим котлом и тем, в чей вектор структуры записывается (distance)
  134.  
  135. 	unsigned long long s=0;
  136. 	while(A[empty].mass<b){//Пока, собственно, котёл не заполнится
  137. 	/*	for(int i=0; i<n;i++){//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  138. 			cout<<A[i].mass<<" ";
  139. 		}cout<<endl;*/
  140.  
  141. 		unsigned long long a=Min_way(A,A[empty].number, A[empty].number);//Вызываем функцию, которая находит минимальное расстояние от нужного котла до того, в котором есть топливо
  142. 		//В том числе, с перекачкой через другие котлы
  143. 		if(A[near_tube].mass-b+A[empty].mass<b){//Если даже после перекачки в котле всё ещё не будет хватать топлива
  144. 			A[empty].mass+=A[near_tube].mass-b;
  145. 			s+=a*(A[near_tube].mass-b);
  146. 			A[near_tube].mass=b;
  147. 		}
  148. 		else{
  149. 			int tmp=b-A[empty].mass;
  150. 			A[near_tube].mass-=tmp;//Да, это уже не влияет на дальнейшее решение. Просто мне показалось правильнее, чтобы программа заканчивала работу с реальным количеством топлива в котлах
  151. 			A[empty].mass=b;
  152. 			s+=a*tmp;
  153. 		}
  154. 		//cout<<"   : "<<a<<" "<<A[empty].mass<<" "<<near_tube<<endl<<endl;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  155. 	}
  156.  
  157. 	cout<<s*c;//Вывод ответа
  158. 	return 0;
  159. }
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/8T12XQ
Топливо с комментариями
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!