# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
124609 | deinfreund | Sightseeing (NOI14_sightseeing) | C++14 | 3604 ms | 97896 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;
vector<vector<pair<int, int>> > conns;
vector<int> ind;
vector<bool> needed;
vector<int> res;
int remaining;
void dijkstra(int node, int maxcost, int cost){
//cerr << "@" << node << " for " << cost << " until " << maxcost << endl;
if (needed[node]){
remaining --;
res[node] = cost;
}
if (remaining <= 0) return;
int i = ind[node];
for (;ind[node] < conns[node].size() && conns[node][ind[node]].first < maxcost;){
i = ind[node] ++;
dijkstra(conns[node][i].second, min(maxcost, (i < (conns[node].size() - 1)) ? conns[node][i + 1].first : 1000000000), max(conns[node][i].first, cost));
if (remaining <= 0) return;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int nodes, edges, targets;
cin >> nodes >> edges >> targets;
conns.resize(nodes);
ind.resize(nodes);
for (int i = 0; i < edges; i++){
int a, b, c;
cin >> a >> b>> c;
a--; b--; c *= -1;
conns[a].push_back({c,b});
conns[b].push_back({c, a});
}
for (int i = 0 ; i < nodes; i++){
sort(conns[i].begin(), conns[i].end());
}
res.resize(nodes);
vector<int> trg(targets);
needed.resize(nodes);
remaining = targets;
for (int i = 0; i < targets; i++){
cin >> trg[i]; trg[i]--;
needed[trg[i]] = 1;
}
dijkstra(0, 1000000000, -1000000000);
for (int i = 0; i < targets; i++){
cout << -res[trg[i]] << endl;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |