Submission #197514

#	Time	Username	Problem	Language	Result	Execution time	Memory
197514		handlename	Sightseeing (NOI14_sightseeing)	C++17	15 / 25	3576 ms	207656 KiB

sightseeing

#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';
    }
}

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