Submission #1138546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138546		mnbvcxz123	Treasure Hunt (CCO24_day1problem1)	C++20	25 / 25	2335 ms	118136 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<ll,ll>;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int>a(n);
    for(int&i:a)cin>>i;
    vector<vector<pi>>g(n);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        --a,--b;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    priority_queue<pi>q;
    for(int i=0;i<n;++i)
        q.push({a[i],i});
    vector<int>ans(n,-1);
    while(!q.empty()){
        int x=q.top().second;
        int c=q.top().first;
        q.pop();
        if(ans[x]==-1)ans[x]=c;
        else if(ans[x]!=-1 and c>ans[x])ans[x]=c;
        else continue;
        for(const auto&[i,w]:g[x])
            q.push({c-w,i});
    }
    for(int i=0;i<n;++i)
        cout<<ans[i]<<'\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8