Submission #124574

#TimeUsernameProblemLanguageResultExecution timeMemory
124574deinfreundSightseeing (NOI14_sightseeing)C++14
0 / 25
3586 ms75772 KiB
#include <bits/stdc++.h> using namespace std; vector<vector<int> > conns; vector<vector<int> > costs; int main(){ int nodes, edges, targets; cin >> nodes >> edges >> targets; conns.resize(nodes); costs.resize(nodes); vector<pair<int, int>> edgeSort; for (int i = 0; i < edges; i++){ int a, b, c; cin >> a >> b>> c; a--; b--; c *= -1; edgeSort.push_back({c, i}); conns[a].push_back(b); costs[a].push_back(c); conns[b].push_back(a); costs[b].push_back(c); } sort(edgeSort.begin(), edgeSort.end()); return 0; int remaining = 0; vector<bool> needed(nodes, 0); vector<int> trg; for (int i = 0 ; i < targets; i++){ remaining ++; int a; cin >> a; a--; needed[a] = 1; trg.push_back(a); } vector<long long> best(nodes, 1000000000000000000LL); priority_queue<pair<long long, int>> pq; pq.push({-1000000000000000000LL,0}); while (true){ int pos, cost; do{ pos = pq.top().second; cost = -pq.top().first; pq.pop(); }while(cost > best[pos]); if (needed[pos]) remaining --; if (remaining == 0) break; for (int i = 0; i < conns[pos].size(); i++){ int c = max(cost, costs[pos][i]); if (c < best[conns[pos][i]]){ best[conns[pos][i]] = c; pq.push({-c, conns[pos][i]}); } } } for (int i = 0; i < targets; i++){ cout << -best[trg[i]] << endl; } }

Compilation message (stderr)

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:49:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < conns[pos].size(); i++){
                     ~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...