Pagini recente » Borderou de evaluare (job #1836343) | Monitorul de evaluare | Borderou de evaluare (job #2203736) | Cod sursa (job #2863966)
#include <bits/stdc++.h>
#define inf 1000000001
using namespace std;
const long long N=2e5+1;
long long n,m;
long long v[N],d[N];
vector <pair<long long,long long>> a[N];
set <pair <long long,long long>> q;
void dijkstra(){
for(long long i=0; i<n; i++){
d[i]=v[i];
q.insert({d[i],i});
}
while(!q.empty()){
long long x=q.begin()->second;
q.erase(q.begin());
for(auto j:a[x]){
long long y=j.first;
long long c=j.second;
if(d[x]+c<d[y]){
q.erase({d[y],y});
d[y]=d[x]+c;
q.insert({d[y],y});
}
}
}
}
int main()
{
cin>>n>>m;
for(long long i=1; i<=m; i++){
long long x,y,c;
cin>>x>>y>>c;
x--;
y--;
a[x].push_back({y,2*c});
a[y].push_back({x,2*c});
}
for(long long i=0; i<n; i++)
cin>>v[i];
dijkstra();
for(long long i=0; i<n; i++)
cout<<d[i]<<" ";
return 0;
}