Submission #1177213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177213		bohun.i	Sightseeing (NOI14_sightseeing)	C++20	15 / 25	2986 ms	302660 KiB

sightseeing

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;

vector<pair<long long, long long> > v[500500];
long long d[500500];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    long long n, m, q, w, e, k;
    cin >> n >> m >> q;
    for (long long i=0;i<m; i++) {
        cin >> w >> e >> k;
        v[w].push_back(make_pair(e, k));
        v[e].push_back(make_pair(w, k));
    }
    for (long long i = 1; i <= n; i++) {
        d[i] = 0;
    }
    d[1]=0;
    priority_queue<pair<long long, long long>> pq;
    pq.push(make_pair(100000000000000, 1));
    while (!pq.empty()) {
        pair<long long, long long> top = pq.top();
        pq.pop();
        if (top.first >= d[top.second]) {
            d[top.second] = top.first;
            for (long long i = 0; i < v[top.second].size(); i++) {
                if (d[v[top.second][i].first] < min(v[top.second][i].second, d[top.second])) {
                    d[v[top.second][i].first] = min(v[top.second][i].second, d[top.second]);
                    pq.push({min(v[top.second][i].second, d[top.second]), v[top.second][i].first});
                }

            }
        }
    }
    for (long long i = 1; i <= q; i++) {
        cin>>k;
        cout<<d[k]<<"\n";
    }
    //cout <<"Q"<< endl;
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 0 / 10