Submission #51213

#TimeUsernameProblemLanguageResultExecution timeMemory
51213KubalionzzaleSightseeing (NOI14_sightseeing)C++14
15 / 25
3545 ms105428 KiB
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <functional> std::vector< std::vector< std::pair<int, int> > > g(500010); int ans[500010] = { 0 }; void bfs() { std::set<std::pair<int, int> , std::greater<std::pair<int, int> > > set; set.insert(std::make_pair(2e5, 0)); bool visited[500010] = { 0 }; while (set.empty() == false) { std::pair<int, int> top = *set.begin(); int curNode = top.second; int curVal = top.first; set.erase(set.begin()); // std::cout << curNode << " " << curVal << "\n"; if (visited[curNode]) continue; else visited[curNode] = 1; for (int i = 0; i < g[curNode].size(); ++i) { std::pair<int, int> next = g[curNode][i]; int nextVal = next.first; int nextNode = next.second; if (!visited[nextNode]) { ans[nextNode] = std::max(ans[nextNode], std::min(nextVal, curVal)); set.insert(std::make_pair(std::min(nextVal, curVal), nextNode)); } } } } int main() { int n, m, q; std::cin >> n >> m >> q; while (m--) { int x, y, quality; std::cin >> x >> y >> quality; --x, --y; g[x].push_back(std::make_pair(quality, y)); g[y].push_back(std::make_pair(quality, x)); } bfs(); int node[500010]; for (int i = 0; i < q; ++i) { std::cin >> node[i]; } for (int i = 0; i < q; ++i) { std::cout << ans[node[i] - 1] << "\n"; } }

Compilation message (stderr)

sightseeing.cpp: In function 'void bfs()':
sightseeing.cpp:31:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[curNode].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...