| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 124544 | AdOjis485 | Sightseeing (NOI14_sightseeing) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//
// main.cpp
// sightseeing
//
// Created by AdOjis485 on 03.07.19.
// Copyright © 2019 AdOjis485. All rights reserved.
//
#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;
}