This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int ar[n+5]={};
int mx[n+5]={};
for(int i=0;i<n;i++){
cin>>ar[i];
}
priority_queue<pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int> > >pq;
for(int i=1;i<n;i++){
pq.push({ar[0]+ar[i],i});
mx[i]=ar[0]+ar[i];
}
int vis[n+5]={};
int ans=0;
int i=n-1;
while(i){
int a=pq.top().first;
int b=pq.top().second;
pq.pop();
if(vis[b]==0){
i--;
//cout<<b<<" "<<a<<" "<<i<<endl;
ans+=a;
vis[b]=1;
for(int j=0;j<n;j++){
if(vis[j]==0){
if(ar[b]+ar[j]<mx[j]){
mx[j]=ar[b]+ar[j];
pq.push({mx[j],j});
}
}
}
}
}
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |