Submission #197514

#TimeUsernameProblemLanguageResultExecution timeMemory
197514handlenameSightseeing (NOI14_sightseeing)C++17
15 / 25
3576 ms207656 KiB
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    vector<pair<int,int> > adjList[500001]; // node, weight
    int v,e,q;
    cin>>v>>e>>q;
    for (int i=0;i<e;i++){
        int a,b,d;
        cin>>a>>b>>d;
        adjList[a].push_back(make_pair(b,d));
        adjList[b].push_back(make_pair(a,d));
    }
    priority_queue<pair<int,int> > pq; // distance, node
    int dist[500001];
    memset(dist,0,sizeof(dist));
    pq.push(make_pair(1000000000,1)); dist[1] = 1000000000;
    while (!pq.empty()){
        pair<int,int> c = pq.top();
        pq.pop();
        if (c.first != dist[c.second]) continue;
        for (auto i : adjList[c.second]){
            if (dist[i.first] < min(c.first,i.second)){
                dist[i.first] = min(c.first,i.second);
                pq.push(make_pair(dist[i.first], i.first));
            }
        }
    }
    for (int i=0;i<q;i++){
        int x;
        cin>>x;
        cout<<dist[x]<<'\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...