Advertisement
rotti321

Skiing II

Feb 27th, 2022
37
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int H[2<<17];
  4. vector<int>G[2<<17];
  5. long D[2<<17];
  6. main(){
  7. int n,m;
  8. scanf("%d%d",&n,&m);
  9. for(int i=0;i<n;i++)scanf("%d",&H[i]);
  10. for(int i=0;i<m;i++){
  11. int u,v;
  12. scanf("%d%d",&u,&v);
  13. u--,v--;
  14. G[u].push_back(v);
  15. G[v].push_back(u);
  16. }
  17. priority_queue<pair<long,int>>Q;
  18. Q.push({H[0],0});
  19. fill(D,D+n,-1e18);
  20. D[0]=H[0];
  21. long ans=0;
  22. while(!Q.empty()){
  23. auto[d,u]=Q.top();
  24. Q.pop();
  25. if(d<D[u])continue;
  26. ans=max(ans,d-H[u]);
  27. for(int v:G[u]){
  28. int c=min(H[u]-H[v],0);
  29. if(d+c>D[v])D[v]=d+c,Q.push({d+c,v});
  30. }
  31. }
  32. printf("%ld\n",ans);
  33. }
Advertisement
RAW Paste Data Copied
Advertisement