fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. struct boil{
  7. 	int mass=0;
  8. 	int len=0;
  9. 	char n/*new*/='y';//yes
  10. 	char visit='n';//no
  11. 	vector <int> link;
  12. 	vector <int> dis;
  13. };
  14.  
  15. int main() {
  16. 	int N,M,B,C;
  17. 	cin>>N>>M>>B>>C;
  18. 	boil A[N];
  19. 	int need;
  20. 	for(int i=0;i<N;i++){
  21. 		cin>>A[i].mass;
  22. 		if(A[i].mass<B)need=i;
  23. 	}
  24. 	int a,b,s;
  25. 	while(cin>>a>>b>>s){
  26. 		a--;
  27. 		b--;
  28. 		A[a].link.push_back(b);
  29. 		A[a].dis.push_back(s);
  30. 		A[b].link.push_back(a);
  31. 		A[b].dis.push_back(s);
  32. 	}
  33. 	queue <int> A_tmp;
  34. 	A_tmp.push(need);
  35. 	A[need].n='n';
  36. 	int ans=0;
  37. 	while(!(A_tmp.empty())){
  38. 		int u=A_tmp.front();
  39. 		A_tmp.pop();
  40. 		A[u].visit='y';
  41. 		for(int i=0;i<A[u].link.size();i++){
  42. 			if(A[A[u].link[i]].visit=='n')
  43. 				A_tmp.push(A[u].link[i]);
  44. 			if(A[A[u].link[i]].len>A[u].len+A[u].dis[i] || A[A[u].link[i]].n=='y'){
  45. 				A[A[u].link[i]].len=A[u].len+A[u].dis[i];
  46. 				A[A[u].link[i]].n='n';
  47. 			}
  48. 		}
  49. 	}
  50. 	while(A[need].mass<B){
  51. 		int m=0;
  52. 		for(int i=0; i<N;i++){
  53. 			if((A[i].len<A[m].len|| A[m].mass<=B) && i!=need && A[i].mass>B)
  54. 				m=i;
  55. 		}
  56. 		if(A[need].mass+(A[m].mass-B)<=B){
  57. 			ans+=A[m].len*(A[m].mass-B);
  58. 			A[need].mass+=A[m].mass-B;
  59. 			A[m].mass=B;
  60. 		}
  61. 		else{
  62. 			ans+=A[m].len*(B-A[need].mass);
  63. 			int b=B-A[need].mass;
  64. 			A[need].mass=B;
  65. 			A[m].mass-=B-A[need].mass;
  66. 		}
  67. 	}
  68. 	cout<<ans*C;
  69. 	return 0;
  70. }
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/dBjy2Z
Топливо через алгоритм Дейкстры
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!