Advertisement
rotti321

Skiing Stack

Mar 4th, 2022
850
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. stack<int>st;
  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.         st.push(i);
  21.     while(st.size())
  22.     {
  23.         int u=st.top();
  24.         st.pop();
  25.         for(auto v:e[u]) ///v este vecin a lui u
  26.         {
  27.             int c;
  28.             if(a[v]>a[u]) ///calc traseul de la v->u
  29.                 c=a[v]-a[u];
  30.             else
  31.                 c=2*(a[v]-a[u]);
  32.             c+=d[u]; /// se calculeaza costul traseului v->u->...
  33.      
  34.             if(c>d[v]) ///am gasit un cost mai bun
  35.             {
  36.                 d[v]=c; ///actualizez costul v->...
  37.                 st.push(v); ///adaug nodul v in stiva
  38.             }
  39.         }
  40.     }
  41.  
  42.     cout<<d[1]<<'\n';
  43.     return 0;
  44. }
  45.  
Advertisement
RAW Paste Data Copied
Advertisement