fork(1) 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){//cout<<from+1<<"->"<<A[i].number+1<<"-->";//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  19. 	/*for(int l=0; l<visit.size(); l++){
  20. 		cout<<visit[l]<<" ";
  21. 	}cout<<endl;*/
  22.  
  23.  
  24. 	if(A[i].mass>b){
  25. 		/*int need=0;
  26. 		for(int j=0; j<A[i].distance.size() && need==0; j++){
  27. 			if(A[from].address[j]->number==i)need=j;
  28. 		}//cout<<A[from].distance[need];
  29. 		*/
  30. 		near_tube=A[i].number;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  31. 		return 0;//A[from].distance[need];
  32. 	}
  33.  
  34.  
  35. 	int min=0;
  36. 	near_tube=0;//Возможно, надо убрать. Может зануляться при рекурсии ненужный раз
  37.  
  38.  
  39. 	bool t=0,t2=1;//t=1;->Ко второму !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  40. 	//for(auto j: A[i].distance){
  41. 		for(int j=0; j< A[i].distance.size(); j++){
  42. 			t2=true;//cout<<"/"<<A[i].address[j]->number+1<<"/";
  43. 			for(int u=0; u<visit.size();u++){
  44. 				if(visit[u]==A[i].address[j]->number){
  45. 					t2=false;
  46. 				}
  47. 			}
  48. 		//	for(int u=0; u<A[empty].address.size()&& A[i].number!=A[empty].number; u++)
  49. 		//		if(A[i].address[j]->number==A[empty].address[u]->number)t2=false;
  50. 			if(A[i].address[j]->number==A[empty].number)t2=false;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  51. 		if(A[i].distance[min]>=A[i].distance[j] && A[i].address[j]->number!=from && t2){//Если в котёл, где одна труба == b?//= нужно. Без него нет t, видимо
  52. 			min=j;
  53. 			t=1;//Ко второму. Подумать ещё!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  54. 		}//<<" ";//cout<<min<<" ";
  55. 	}
  56. 	//cout<<min<<"`";
  57. 	/*
  58. 	visit.push_back(A[i].number);
  59.  
  60. 	for(int k=0; k<visit.size() && t; k++){
  61. 		if(visit[k]==A[i].address[min]->number){
  62. 			t=false;
  63. 		}
  64. 	}
  65. 	*/
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76. 	if(t==0 && A[i].distance.size()==1){// Может, и не надо. Такое и при минимуме частично могло проверяться 
  77. 		if(A[i].address[0]->mass>b){
  78. 			near_tube=A[i].address[0]->number;
  79. 			return A[i].distance[0];
  80. 		}
  81. 		else{
  82. 			return -1;
  83. 		}
  84. 	}
  85. 	else if(t==0){
  86. 		return -1;
  87. 	}
  88. 	else if(A[i].address[min]->mass==b){
  89.  
  90.  
  91. 		//visit.push_back(A[i].number);//(A[i].address[j]->number)
  92.  
  93.  
  94. 	//	for(int l=0; l<visit.size(); l++){
  95. 	//		cout<<visit[l]<<" ";
  96. 	//	}cout<<endl;
  97.  
  98.  
  99.  
  100. 		long long min2;
  101. 		bool t1=true;
  102.  
  103. 		for(int k=0; k<visit.size() && t1; k++){
  104. 			if(visit[k]==A[i].address[min]->number)t1=false;
  105. 		}
  106. 		if(A[i].address[min]->number==from)t1=false;
  107. 		if(!t1){
  108. 			t1=true;
  109. 			for(int k=0; k<visit.size() && t1; k++){
  110. 				if(visit[k]!=A[i].address[min]->number && A[i].address[k]->number!=from){
  111. 					t1=false;
  112. 					min=k;
  113. 				}
  114. 			}
  115. 		}
  116. 		if(!t1)return -1;
  117. 		/*else{
  118. 			min2=Min_way(A,A[i].address[min]->number,A[i].number)+A[i].distance[min];
  119. 		}*/
  120. 		min2=Min_way(A,A[i].address[min]->number,A[i].number);
  121. 		if(min2>=0)min2+=A[i].distance[min];//Да-да, одно и тоже, подумать зачем.
  122. 		//min2=1000;//ДАааааа, оно тут так просто работает! Но неееет, нужно же как-то сделать первый элемент! 
  123.  
  124. 		int n=near_tube;//n- потому что near!
  125. 		int n1=near_tube;//n1- потому что n работает частично, но всё ещё near!
  126. 			vector<int> v_of_n_tubes;//vector of near tubes
  127.  
  128.  
  129. 		//	cout<<"("<<min2<<","<<t1<<")"<<"m"<<"b ";//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  130.  
  131.  
  132. 		//	int min2=Min_way(A,A[i].address[min]->number,A[i].number)+A[i].distance[min];
  133. 			//v_of_n_tubes.push_back(near_tube);
  134.  
  135. 		//int vont=-1;//value of near tubes
  136.  
  137. 		for(int j=0; j<A[i].distance.size(); j++){
  138. 			if(j!=min && A[i].address[j]->mass>=b){
  139. 			if(A[i].address[j]->mass>=b && A[i].address[j]->number!=from){
  140. 				visit.push_back(A[i].number);//Второй раз!!!!!!!!!!!!!!!!!!!!!!!!Во втором варианте, в начале функции
  141. 				long long a=0;
  142. 				t1=true;bool t3=true;
  143. 				for(int k=0; k<visit.size() && t1; k++){
  144. 					if(visit[k]==A[i].address[j]->number)t3=false;
  145. 				}
  146.  
  147. 		//		for(int u=0; u<A[empty].address.size() && A[i].number!=A[empty].number; u++)
  148. 		//			if(A[i].address[j]->number==A[empty].address[u]->number)t3=false;
  149. 				if(A[i].address[j]->number==A[empty].number)t3=false;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  150.  
  151.  
  152. 				if(t1 && t3){
  153. 					a=Min_way(A,A[i].address[j]->number,A[i].number);
  154. 				}
  155. 				else return-1;
  156.  
  157.  
  158. 				//if(min!=j)v_of_n_tubes.push_back(near_tube);//?????????????????????????????????????????????????????????????
  159. 				visit.push_back(A[i].address[j]->number);//По рекурсии сюда вряд ли зайдёт, смысл?//Возможно, лишнее 
  160.  
  161. 				//	cout<<a<<"->";
  162.  
  163. 				//a=Min_way(A,A[i].address[j]->number,A[i].number);//==0? 0 :
  164. 				if(a>=0)a+=(A[i].distance[j]);//cout<<a<<" "<<A[i].distance[j]<<" "<<A[i].number+1<<" ";//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  165. 				if(a>=0 && min2>=a && A[near_tube].mass>b || (n==-1? false : A[n].mass==b) ||min2<0 /*A[i].address[j]->mass<=b||*/){//По сути, == b
  166. 				//if(A[i].address[j]->mass!=b)
  167. 					min2=a;
  168. 					n=-1;//cout<<A[near_tube].mass;//cout<<"  e  ";
  169. 				//	if(min!=j)vont=j;//Если минимум-минимум.
  170. 					//vont++;
  171. 					//v_of_n_tubes.push_back(near_tube);
  172. 					n1=near_tube;
  173. 				}//cout<<"m:"<<min2<<"       ";
  174.  
  175. 			//	cout<<"("<<a<<","<<t1<<")"<<"b ";//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  176.  
  177.  
  178.  
  179. 				visit.clear();
  180. 			}
  181. 			}
  182. 			//else v_of_n_tubes.push_back(near_tube);//???????????????????????????????????????????????????????????????????????
  183. 		}//for(int i=0;i<v_of_n_tubes.size();i++)//cout<<v_of_n_tubes[i]<<" - "<<vont<<"    ";
  184. 		//visit.clear();
  185. 		near_tube=n1;//(vont>=0? v_of_n_tubes[vont] : n);//cout<<endl;
  186. 		return min2;
  187. 			/*
  188. 		else{
  189. 			visit.clear();
  190. 			return -1;
  191. 		}*/
  192.  
  193.  
  194. 	}
  195. 	else if(A[i].address[min]->mass<b){// Не должен- в визите есть, по идее// Но проверка визитом сюда не должна заходить, значит — пусть будет
  196. 		return -1;
  197. 	}
  198. 	else{
  199. 		near_tube= A[i].address[min]->number;
  200. 		return A[i].distance[min];
  201. 	}
  202. }
  203.  
  204. int main() {//cout<<3;
  205. 	cin>>n;//cin.get();
  206. 	cin>>m;//cin.get();
  207. 	cin>>b;//cin.get();
  208. 	cin>>c;//cin.get();
  209. 	boil A[n];
  210. //	cin.ignore(32767, '\n' || ' ');
  211. 	for(int i=0; i<n; i++){//cout<<5;
  212. 		int a;//cin.ignore(32767, '\n' || ' ');
  213. 		cin>>a;//cin.clear();//cout<<5;
  214. 		//scanf("%c", a);
  215. 		A[i].mass=a;
  216. 		A[i].number=i;
  217. 		if(A[empty].mass>a)empty=i;
  218. 	}
  219. int d;
  220. 	//for(int i=0; i<m; i++){//cout<<9;//m+1, там тест странный.
  221. 	while(cin>>d){
  222. 			int a,g;
  223. 			cin>>a>>g;
  224. 		//	cin>>a;//cin.get();
  225. 		//	cin>>d;//cin.get();
  226. 		//	cin>>g;//cout<<5;
  227. //	cout<<a<<" "<<d<<" "<<g<<endl;
  228. 			A[d-1].address.push_back(&A[a-1]);//cout<<5;
  229. 			A[a-1].address.push_back(&A[d-1]);
  230. 			A[a-1].distance.push_back(g);
  231. 			A[d-1].distance.push_back(g);
  232. 	//cout<<8;
  233. 	}
  234.  
  235.  
  236.  
  237. 	//int i=0;
  238.  
  239.  
  240.  
  241.  
  242.  
  243. 	unsigned long long s=0;//cout<<(A[0].address[0])->mass;
  244. 	while(A[empty].mass<b){
  245. 		//boil* tmp=A[empty].A[empty].address[Min_way(A,empty)]->mass;
  246.  
  247. 		unsigned long long a=Min_way(A,A[empty].number, -1);//cout<<a<<" ";a=Min_way(A, A[empty].number, -1);cout<<a<<" ";break;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  248. 		if(A[near_tube].mass-b+A[empty].mass<b){//< ??
  249. 			A[empty].mass+=A[near_tube].mass-b;//number
  250. 			s+=a*(A[near_tube].mass-b);
  251. 			A[near_tube].mass=b;
  252. 			//'d'//distance
  253. 		}
  254. 		else{
  255. 			int tmp=b-A[empty].mass;
  256. 			A[near_tube].mass-=tmp;//Можно убрать, по идее, всё равно конец цикла
  257. 			A[empty].mass=b;
  258. 			s+=a*tmp;
  259. 		}
  260. 	//	cout<<"   : "<<a<<" "<<A[empty].mass<<" "<<near_tube<<endl;
  261. 	//cout<<s<<" ";
  262. 	}//cout<<A[empty].distance[Min_way(A,empty)]<<" ";
  263.  
  264.  
  265.  
  266.  
  267.  
  268.  
  269. 	//for(int i=0; i<3;i++)cout<<A[3].address[i]->number+1<<" ";cout<<endl;
  270.  
  271.  
  272.  
  273.  
  274.  
  275.  
  276. /*
  277.  
  278.  
  279. 	for(int i=0; i<8; i++){
  280. 		cout<<A[i].mass<<" ";
  281. 	}cout<<endl;
  282.  
  283.  
  284.  
  285.  
  286.  
  287. 	cout<<"  "<<Min_way(A,3,-1)<<" "<<endl;
  288. 	//cout<<Min_way(A,6,1)<<" "<<A[6].mass<<endl;
  289.  
  290.  
  291.  
  292. 	*/
  293. 	//cout<<A[3].address[1]->number+1;
  294.  
  295. 	/*
  296. 	for(int i=0; i<4;i++){
  297. 		//boil* tmp=A[empty].A[empty].address[Min_way(A,empty)]->mass;
  298.  
  299. 		int a=Min_way(A,A[empty].number, -1);
  300. 		if(A[near_tube].mass-b+A[empty].mass<=b){//< ?
  301. 			A[empty].mass+=((A[near_tube].mass)-b);//number
  302. 			s+=a*((A[near_tube].mass)-b);
  303. 			(A[near_tube].mass)=b;
  304. 			//'d'//distance
  305. 		}
  306. 		else{
  307. 			int tmp=b-A[empty].mass;
  308. 			A[near_tube].mass-=tmp;//Можно убрать, по идее, всё равно конец цикла
  309. 			A[empty].mass=b;
  310. 			s+=a*tmp;
  311. 		}
  312. 		cout<<"   : "<<a<<" "<<A[empty].mass<<" "<<near_tube<<endl;
  313. 	}
  314.  
  315. 	*/
  316.  
  317.  
  318.  
  319. 	cout<<s*c;
  320.  
  321. //	cout<<" "<<Min_way(A,empty)<<" "<< A[empty].distance[Min_way(A,empty)];
  322. 	return 0;
  323. }
  324.  
  325.  
  326. /*		int tmp=((A[empty].address[Min_way(A,empty)])->mass)-b;
  327. 		A[empty].address[Min_way(A,empty)]->mass-=b;
  328. 		A[empty].mass+=tmp;//number
  329. 		*/
  330.  
  331.  
  332.  
  333. 				//cin.putback(' ');cin.putback('4');cin.putback('\n');
  334.  
  335. 			/*bool t=true;
  336. 			do{
  337. 				g=cin.peek()-48;cout<<" "<<g;cout<<3<<" ";
  338. 				if(g!=-16 && i==m-1){//==
  339. 					t=false;
  340. 					cin.ignore(2,'\n');cout<<5;
  341. 					cin.clear();
  342. 				}
  343. 				if(!t){
  344. 					string str;
  345. 					scanf("%s", str);
  346.  
  347. 					//cin.putback(EOF);
  348. 					cin.clear();
  349.  
  350. 				}
  351. 				if(t){
  352. 					char a;
  353. 					cin.get(a);
  354. 				}
  355. 			}while(g==-16 && t);*/
  356. 		//	cout<<a<<" "<<d<<" "<<g<<"\n";
  357.  
  358.  
  359.  
  360.  
  361. 	/*		int a,d,g;
  362. 			cin>>a;
  363. 			cin>>d;
  364. 			cin>>g;
  365. 			cout<<a<<" "<<d<<" "<<g<<"\n";
  366. 			A[d-1].address.push_back(&A[a-1]);//cout<<5;
  367. 			A[a-1].address.push_back(&A[d-1]);
  368. 			A[a-1].distance.push_back(g);
  369. 			A[d-1].distance.push_back(g);*/
  370.  
  371. //int* N=&n;
  372. /*	scanf("%d", &n);//cout<<n;//int* M=&m;
  373. 	scanf("%d", &m);//cout<<m;
  374. 	scanf("%d", &b);
  375. 	scanf("%d", &c);
  376. 		cout<<n<<m<<b<<c;
  377.  
  378. 	boil A[n];
  379. 	int empty=0;
  380.  
  381. 	for(int i=0; i<n; i++){
  382. 		int a;
  383. 		scanf("%d", a);
  384. 		A[i].mass=a;
  385. 		A[i].number=i;
  386. 		if(A[empty].mass>a)empty=i;
  387. 	}
  388.  
  389.  
  390. 	for(int i=0; i<m; i++){//cout<<9;
  391. 			int a,d,g;
  392. 			scanf("%d", a);
  393. 			scanf("%d", d);
  394. 			scanf("%d", g);
  395. 			A[d-1].address.push_back(&A[a-1]);//cout<<5;
  396. 			A[a-1].address.push_back(&A[d-1]);
  397. 			A[a-1].distance.push_back(g);
  398. 			A[d-1].distance.push_back(g);
  399. 	}*/
  400.  
  401. /*	cin>>n;
  402. 	cin>>m;
  403. 	cin>>b;
  404. 	cin>>c;
  405.  
  406. 	for(int i=0; i<n; i++){
  407. 		int a;
  408. 		cin>>a;
  409. 	}
  410.  
  411. 	for(int i=0; i<m; i++){//cout<<9;
  412. 			int a,d,g;
  413. 			cin>>a;
  414. 			cin>>d;
  415. 			cin>>g;
  416. 	}cout<<4;
  417. 	boil A[n];
  418. 	int empty=0;
  419. */
  420.  
  421.  
  422.  
  423.  
  424. 		/*	int b=Min_way(A,A[i].address[0]->number,A[i].number);
  425. 			int index=-1;//Тоже ?
  426. 			for(int j=0; j<A[i].distance.size(); j++){
  427. 				if(A[i].number!=from){
  428. 					int a=Min_way(A,A[i].address[j]->number,A[i].number);//==0? 0 :;
  429. 					if(a>0 && (b>0? a<b : 10000)){//Да-да, 10000 -такое тут 
  430. 						b=a;
  431. 						index=j;
  432. 					}
  433. 				}
  434. 			}min2=b+A[i].distance[index];*/
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/qJgpZT
Топливо черновик
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!