Submission #1279204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279204		3m17	Treasure Hunt (CCO24_day1problem1)	C++20	25 / 25	1449 ms	119688 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int Nmax = 1e6 + 27;
const int SZ = 600;
const int LogN = 18;
const int MOD = 1e9 + 7;

int n , m;
int v[Nmax] , dist[Nmax];

priority_queue <pair <int , int> , vector<pair <int , int>> , greater <pair  <int , int>>> Q;
vector <pair <int , int>> graph[Nmax];

void Dij ()
{
    for (int i = 1 ; i <= n ; i++)
    {
        dist[i] -= v[i];
        Q.push({dist[i] , i});
    }

    while(!Q.empty())
    {
        int u = Q.top().second;
        Q.pop();
        for (pair <int , int> v : graph[u])
        {
            //if(v.first == 2) cout << v.second << ' ' << dist[u] + v.second << '\n';
            if(dist[v.first] > dist[u] + v.second)
            {
                dist[v.first] = dist[u] + v.second;
                Q.push({dist[v.first] , v.first});
            }
        }
    }
}

main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++)
    cin >> v[i];

    for (int i = 1 ; i <= m ; i++)
    {
        int u , v , c;
        cin >> u >> v >> c;
        graph[u].push_back({v , c});
        graph[v].push_back({u , c});
    }

    Dij();
    for (int i = 1 ; i <= n ; i++) cout << -dist[i] << '\n';
}

Compilation message (stderr)

Main.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main()
      | ^~~~

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