Submission #103438

#	Time	Username	Problem	Language	Result	Execution time	Memory
103438		SecretAgent007	Sightseeing (NOI14_sightseeing)	C++17	9 / 25	3542 ms	180164 KiB

sightseeing

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

#define int long long
#define double long double

const int INF = 9223372036854775807;

vector< vector< pair< int, int > > > Graph;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int v, e, q;
    cin >> v >> e >> q;

    Graph.resize(v+1);

    for(int i = 0; i < e ; i++){
        int a, b, c;
        cin >> a >> b >> c;
        Graph[a].push_back(make_pair(b,c));
        Graph[b].push_back(make_pair(a,c));
    }

    vector< int > dist(v+1,-INF);

    priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;

    pq.push(make_pair(INF,1));

    while(!pq.empty()){

        pair<int, int> p = pq.top();

        int a = p.first;
        int b = p.second;

        pq.pop();

        if(dist[b] > a) continue;

        for(auto c : Graph[b]){
            if(dist[c.first] < min(a,c.second)){
                dist[c.first] = min(a,c.second);
                pq.push(make_pair(dist[c.first],c.first));
            }
        }
    }

    while(q--){
        int a;
        cin >> a;
        cout << dist[a] << '\n';
    }
}
/*
4 4 2
1 2 10
1 3 30
2 4 20
3 4 5
3
4
*/

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