# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
124517 | streifi | 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.
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
struct edge {
int v, w;
bool operator<(const edge &other) const {
return w < other.w;
}
};
int V, E, Q;
vector< vector<edge> > adj;
vector<int> dist;
void dijkstra(int start) {
priority_queue<edge> pq;
dist.assign(V, 0);
dist[start] = INF;
pq.push({start, INF});
while (pq.size()) {
edge cur = pq.top();
pq.pop();
if (cur.w < dist[e.v])
continue;
for (edge e: adj[cur.v]) {
int newdist = min(cur.w, e.w);
if (newdist > dist[e.v]) {
dist[e.v] = newdist;
pq.push({e.v, newdist});
}
}
}
}
signed main() {
cin >> V >> E >> Q;
adj.resize(V);
for (int e = 0; e < E; ++e) {
int u, v, q;
cin >> u >> v >> q;
adj[u-1].push_back({v-1, q});
adj[v-1].push_back({u-1, q});
}
dijkstra(0);
for (int q = 0; q < Q; ++q) {
int X;
cin >> X;
cout << dist[X-1] << endl;
}
}