# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
242748 | 2020-06-29T08:48:36 Z | SamAnd | Sightseeing (NOI14_sightseeing) | C++17 | 3500 ms | 220736 KB |
#include <bits/stdc++.h> using namespace std; #define m_p make_pair #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define fi first #define se second typedef long long ll; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnf(2106); const int N = 500005, INF = 1000000009; struct ban { int x, d; ban(){} ban(int x, int d) { this->x = x; this->d = d; } }; bool operator<(const ban& a, const ban& b) { return a.d < b.d; } int n, m; vector<ban> a[N]; bool c[N]; int ans[N]; void prr() { priority_queue<ban> q; q.push(ban(1, INF)); while (1) { ban t; do { if (q.empty()) return; t = q.top(); q.pop(); } while (c[t.x]); c[t.x] = true; ans[t.x] = t.d; for (int i = 0; i < a[t.x].size(); ++i) { ban h = a[t.x][i]; h.d = min(h.d, t.d); q.push(h); } } } void solv() { int qq; scanf("%d%d%d", &n, &m, &qq); for (int i = 0; i < m; ++i) { int x, y, z; scanf("%d%d%d", &x, &y, &z); a[x].push_back(ban(y, z)); a[y].push_back(ban(x, z)); } prr(); while (qq--) { int x; scanf("%d", &x); printf("%d\n", ans[x]); } } int main() { #ifdef SOMETHING freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); #endif // SOMETHING //ios_base::sync_with_stdio(false), cin.tie(0); solv(); return 0; } //while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 12032 KB | Output is correct |
2 | Correct | 13 ms | 12032 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 12288 KB | Output is correct |
2 | Correct | 12 ms | 12160 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 54 ms | 15224 KB | Output is correct |
2 | Correct | 52 ms | 14584 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3569 ms | 220736 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |