fork download
  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
stdin
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
102