Advertisement
rotti321

Skiing

Feb 27th, 2022
913
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.74 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=200005;
  4. int n,m,a[N],d[N];
  5. queue<int>q;
  6. vector<int>e[N];
  7. int main()
  8. {
  9.     scanf("%d%d",&n,&m);
  10.     for(int i=1;i<=n;i++)
  11.         scanf("%d",&a[i]);
  12.     for(int i=1;i<=m;i++)
  13.     {
  14.         int u,v;
  15.         scanf("%d%d",&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.front();
  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.             cout<<v<<":"<<a[v]<<" "<<u<<":"<<a[u]<<" "<<c<<"->";
  33.             c+=d[u];
  34.             cout<<c<<" old:"<<d[v]<<'\n';
  35.             if(c>d[v])
  36.             {
  37.                 d[v]=c;
  38.                 q.push(v);
  39.                 cout<<"PUSH:"<<v<<"\n";
  40.             }
  41.         }
  42.     }
  43.     printf("%d\n",d[1]);
  44.     return 0;
  45. }
  46.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement