제출 #1197944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197944		12345678	Treasure Hunt (CCO24_day1problem1)	C++20	25 / 25	858 ms	86324 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nx=1e6+5;

int n, m, u, v, w, dp[nx], vs[nx];
vector<pair<int, int>> d[nx];
priority_queue<pair<int, int>> pq;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>dp[i], pq.push({dp[i], i});
    for (int i=1; i<=m; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
    while (!pq.empty())
    {
        auto [cw, u]=pq.top();
        pq.pop();
        if (vs[u]) continue;
        vs[u]=1;
        for (auto [v, w]:d[u]) if (dp[v]<cw-w) dp[v]=cw-w, pq.push({cw-w, v});
    }
    for (int i=1; i<=n; i++) cout<<dp[i]<<'\n';
}

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