# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
168914 | 2019-12-17T06:07:46 Z | YottaByte | Evacuation plan (IZhO18_plan) | C++14 | 5 ms | 816 KB |
#include <iostream> #include <queue> #include <vector> using namespace std; #define ll long long #define sz(x) (int)x.size() #define pii pair < int, int > #define endl "\n" #define METH ios::sync_with_stdio(0); cin.tie(0); #define BEGIN cout << "BEGIN" << endl; #define END cout << "END" << endl; const int N = 1e3; const int mod = 1e9 + 7; /// ANOTHER HASH MOD: 228228227 const int prime = 29; /// ANOTHER HASH PRIME: 997 const int INF = ((long long) 0xCAFEBABE - 1e9 - 4e8); int n, m, k, q; vector < int > bad, dist(N + 1, INF); vector < pii > g[N + 1], querry; inline void purify() { } inline void precalc() { } inline void read() { scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); g[a].push_back({b, c}); g[b].push_back({a, c}); } scanf("%d", &k); for (int i = 1; i <= k; i++) { int a; scanf("%d", &a); bad.push_back(a); } scanf("%d", &q); querry.push_back({0, 0}); for (int i = 1; i <= q; i++) { int a, b; scanf("%d %d", &a, &b); querry.push_back({a, b}); } } void dij(int cur) { priority_queue < pii > pq; pq.push({0, cur}); dist[cur] = 0; while (pq.size()) { cur = pq.top().second; int d = -pq.top().first; pq.pop(); if (d > dist[cur]) { continue; } for (pii i : g[cur]) { int u = i.first; int len = i.second; if (dist[cur] + len < dist[u]) { dist[u] = dist[cur] + len; pq.push({-dist[u], u}); } } } } inline void solve() { if (n <= N && m <= N && q <= N) { for (int i : bad) { dij(i); } for (int i = 1; i <= q; i++) { pii j = querry[i]; printf("%d\n", min(dist[j.first], dist[j.second])); } } } int main() { int t; //scanf("%d", &t); t = 1; //precalc(); while (t--) { //purify(); read(); solve(); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 380 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 3 ms | 476 KB | Output is correct |
6 | Correct | 3 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 376 KB | Output is correct |
11 | Correct | 3 ms | 376 KB | Output is correct |
12 | Correct | 3 ms | 376 KB | Output is correct |
13 | Correct | 3 ms | 472 KB | Output is correct |
14 | Correct | 3 ms | 376 KB | Output is correct |
15 | Correct | 3 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 380 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 3 ms | 476 KB | Output is correct |
6 | Correct | 3 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 376 KB | Output is correct |
11 | Correct | 3 ms | 376 KB | Output is correct |
12 | Correct | 3 ms | 376 KB | Output is correct |
13 | Correct | 3 ms | 472 KB | Output is correct |
14 | Correct | 3 ms | 376 KB | Output is correct |
15 | Correct | 3 ms | 376 KB | Output is correct |
16 | Runtime error | 5 ms | 760 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
17 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 388 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 5 ms | 816 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 380 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 3 ms | 476 KB | Output is correct |
6 | Correct | 3 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 376 KB | Output is correct |
11 | Correct | 3 ms | 376 KB | Output is correct |
12 | Correct | 3 ms | 376 KB | Output is correct |
13 | Correct | 3 ms | 472 KB | Output is correct |
14 | Correct | 3 ms | 376 KB | Output is correct |
15 | Correct | 3 ms | 376 KB | Output is correct |
16 | Runtime error | 5 ms | 760 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
17 | Halted | 0 ms | 0 KB | - |