Submission #124545

#	Time	Username	Problem	Language	Result	Execution time	Memory
124545		AdOjis485	Sightseeing (NOI14_sightseeing)	C++14	15 / 25	3532 ms	92956 KiB

sightseeing

//
//  main.cpp
//  sightseeing
//
//  Created by AdOjis485 on 03.07.19.
//  Copyright © 2019 AdOjis485. All rights reserved.
//

#include <limits>
#include <iostream>
#include <vector>
#include <queue>
#define int int64_t
using namespace std;
/*
bool bfs(int x, int m, vector<vector<pair<int, int>>> adi){
    queue<int> q;
    q.push(0);
    vector<bool> vis(adi.size(), false);
    while(q.size() > 0){
        int cur = q.front();
        q.pop();
        if(!vis[cur]){
            vis[cur] = true;
            for(pair<int, int> next : adi[cur]){
                if(!vis[next.first] && next.second >= m){
                    q.push(next.first);
                }
            }
        }
    }
    return vis[x];
}
*/

vector<int> dijkstra(vector<vector<pair<int, int>>>& adi){
    priority_queue<pair<int, int>> pq;
    pq.push({numeric_limits<int>::max(), 0});
    vector<int> vis(adi.size(), -1);
    while(pq.size() > 0){
        int cur = pq.top().second;
        int cq = pq.top().first;
        pq.pop();
        if(vis[cur] == -1 || vis[cur] < cq){
            vis[cur] = cq;
            for(pair<int, int> next : adi[cur]){
                if(vis[next.first] < cq){
                    pq.push({min(cq, next.second), next.first});
                }
            }
        }
    }
    return vis;
}

signed main() {
    int v, e, q;
    cin >> v >> e >> q;
    vector<vector<pair<int, int>>> adi(v);
    int maxq = 0;
    for(int i = 0; i < e; i ++){
        int v1, v2, qu;
        cin >> v1 >> v2 >> qu;
        v1 --;
        v2 --;
        adi[v1].push_back({v2, qu});
        adi[v2].push_back({v1, qu});
        maxq = max(maxq, qu);
    }
    vector<int> vis = dijkstra(adi);
    for(int i = 0; i < q; i ++){
        int x;
        cin >> x;
        x --;
        /*
        int mi = 0;
        int ma = maxq + 1;
        while(mi < ma - 1){
            int m = (mi + ma) / 2;
            if(bfs(x, m, adi)){
                mi = m;
            }
            else{
                ma = m;
            }
        }
        cout << mi << '\n';
         */
        cout << vis[x] << '\n';
    }
    return 0;
}

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