Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int N=200005;
- int n,m,a[N],d[N];
- queue<int>q;
- vector<int>e[N];
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)
- scanf("%d",&a[i]);
- for(int i=1;i<=m;i++)
- {
- int u,v;
- scanf("%d%d",&u,&v);
- e[u].push_back(v);
- e[v].push_back(u);
- }
- for(int i=1;i<=n;i++)
- q.push(i);
- while(q.size())
- {
- int u=q.front();
- q.pop();
- for(auto v:e[u])
- {
- int c;
- if(a[v]>a[u])
- c=a[v]-a[u];
- else
- c=2*(a[v]-a[u]);
- cout<<v<<":"<<a[v]<<" "<<u<<":"<<a[u]<<" "<<c<<"->";
- c+=d[u];
- cout<<c<<" old:"<<d[v]<<'\n';
- if(c>d[v])
- {
- d[v]=c;
- q.push(v);
- cout<<"PUSH:"<<v<<"\n";
- }
- }
- }
- printf("%d\n",d[1]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement