Submission #1230453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230453		papaulo	Sightseeing (NOI14_sightseeing)	C++20	15 / 25	3579 ms	156372 KiB

sightseeing

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

#define MAXV 500500
#define MAXQ MAXV

int dist[MAXV];
vector<pair<int, int>> adj[MAXV];

int main() {
    int v, e, q;
    cin >> v >> e >> q;
    while(e--) {
        int v1, v2, q;
        cin >> v1 >> v2 >> q;
        adj[v1].push_back({v2, q});
        adj[v2].push_back({v1, q});
    }
    priority_queue<pair<int, int>> pq;
    for(int i=2;i<=v;i++) dist[i]=0;
    dist[1]=1e9;
    pq.push({dist[1], 1});
    while(!pq.empty()) {
        auto pr = pq.top();
        pq.pop();
        int v=pr.second;
        int d=dist[v];
        if(d>pr.first) continue;
        for(auto e : adj[v]) {
            int u=e.first, q=e.second;
            int newd=min(d, q);
            if(newd>dist[u]) {
                dist[u]=newd;
                pq.push({newd, u});
            }
        }
    }
    while(q--) {
        int x;
        cin >> x;
        cout << dist[x] << "\n";
    }
    return 0;
}

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