Advertisement
rotti321

E-Skiing C++

Mar 4th, 2022
522
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=200005;
  4. int n,m,a[N],d[N];
  5. priority_queue<int>q;
  6. vector<int>e[N];
  7. int main()
  8. {
  9.     cin>>n>>m;
  10.     for(int i=1;i<=n;i++)
  11.         cin>>a[i];
  12.     for(int i=1;i<=m;i++)
  13.     {
  14.         int u,v;
  15.         cin>>u>>v;
  16.         e[u].push_back(v);
  17.         e[v].push_back(u);
  18.     }
  19.     for(int i=1;i<=n;i++)
  20.         q.push(i);
  21.     while(q.size())
  22.     {
  23.         int u=q.top();
  24.         q.pop();
  25.         for(auto v:e[u])
  26.         {
  27.             int c;
  28.             if(a[v]>a[u])
  29.                 c=a[v]-a[u];
  30.             else
  31.                 c=2*(a[v]-a[u]);
  32.             c+=d[u];
  33.             if(c>d[v])
  34.             {
  35.                 d[v]=c;
  36.                 q.push(v);
  37.             }
  38.         }
  39.     }
  40.  
  41.     cout<<d[1]<<'\n';
  42.     return 0;
  43. }
  44.  
Advertisement
RAW Paste Data Copied
Advertisement