Submission #1230453

#TimeUsernameProblemLanguageResultExecution timeMemory
1230453papauloSightseeing (NOI14_sightseeing)C++20
15 / 25
3579 ms156372 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...