# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
81106 | 2018-10-23T19:34:48 Z | ToadDaveski | Evacuation plan (IZhO18_plan) | C++14 | 1439 ms | 31812 KB |
#include <bits/stdc++.h> #define ll long long #define fr first #define sc second using namespace std; vector <pair <ll,ll> > v[100001]; ll dp[100001]; priority_queue <pair <ll,ll> > q; int main() { ll n,m,Q,k,i,j; cin>>n>>m; for(i=1;i<=n;i++) dp[i]=1e9; for(i=1;i<=m;i++) { ll x,y,z; cin>>x>>y>>z; v[x].push_back({y,z}); v[y].push_back({x,z}); } cin>>k; for(i=1;i<=k;i++) { ll x,y; cin>>x; q.push({0,x}); dp[x]=0; } while(!q.empty()) { ll from=q.top().sc; ll weight=-q.top().fr; q.pop(); if (dp[from]<weight) continue; for(auto to : v[from]) { if (dp[to.fr]>dp[from]+to.sc) { dp[to.fr]=dp[from]+to.sc; q.push({-(dp[from]+to.sc),to.fr}); } } } cin>>Q; for(i=1;i<=Q;i++) { ll x,y; cin>>x>>y; cout<<min(dp[x],dp[y])<<endl; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 9 ms | 2680 KB | Output is correct |
3 | Correct | 10 ms | 2680 KB | Output is correct |
4 | Correct | 4 ms | 2680 KB | Output is correct |
5 | Correct | 10 ms | 2808 KB | Output is correct |
6 | Correct | 9 ms | 2680 KB | Output is correct |
7 | Correct | 4 ms | 2680 KB | Output is correct |
8 | Correct | 4 ms | 2680 KB | Output is correct |
9 | Correct | 10 ms | 2680 KB | Output is correct |
10 | Correct | 10 ms | 2676 KB | Output is correct |
11 | Correct | 9 ms | 2680 KB | Output is correct |
12 | Correct | 10 ms | 2680 KB | Output is correct |
13 | Correct | 9 ms | 2776 KB | Output is correct |
14 | Correct | 9 ms | 2808 KB | Output is correct |
15 | Correct | 9 ms | 2680 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 9 ms | 2680 KB | Output is correct |
3 | Correct | 10 ms | 2680 KB | Output is correct |
4 | Correct | 4 ms | 2680 KB | Output is correct |
5 | Correct | 10 ms | 2808 KB | Output is correct |
6 | Correct | 9 ms | 2680 KB | Output is correct |
7 | Correct | 4 ms | 2680 KB | Output is correct |
8 | Correct | 4 ms | 2680 KB | Output is correct |
9 | Correct | 10 ms | 2680 KB | Output is correct |
10 | Correct | 10 ms | 2676 KB | Output is correct |
11 | Correct | 9 ms | 2680 KB | Output is correct |
12 | Correct | 10 ms | 2680 KB | Output is correct |
13 | Correct | 9 ms | 2776 KB | Output is correct |
14 | Correct | 9 ms | 2808 KB | Output is correct |
15 | Correct | 9 ms | 2680 KB | Output is correct |
16 | Correct | 597 ms | 9716 KB | Output is correct |
17 | Correct | 1421 ms | 31632 KB | Output is correct |
18 | Correct | 108 ms | 5440 KB | Output is correct |
19 | Correct | 580 ms | 11236 KB | Output is correct |
20 | Correct | 1393 ms | 31812 KB | Output is correct |
21 | Correct | 820 ms | 16524 KB | Output is correct |
22 | Correct | 567 ms | 9096 KB | Output is correct |
23 | Correct | 1385 ms | 31528 KB | Output is correct |
24 | Correct | 1408 ms | 31556 KB | Output is correct |
25 | Correct | 1439 ms | 31600 KB | Output is correct |
26 | Correct | 576 ms | 11236 KB | Output is correct |
27 | Correct | 578 ms | 11272 KB | Output is correct |
28 | Correct | 579 ms | 11208 KB | Output is correct |
29 | Correct | 582 ms | 11280 KB | Output is correct |
30 | Correct | 581 ms | 11236 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 2680 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 420 ms | 15524 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 9 ms | 2680 KB | Output is correct |
3 | Correct | 10 ms | 2680 KB | Output is correct |
4 | Correct | 4 ms | 2680 KB | Output is correct |
5 | Correct | 10 ms | 2808 KB | Output is correct |
6 | Correct | 9 ms | 2680 KB | Output is correct |
7 | Correct | 4 ms | 2680 KB | Output is correct |
8 | Correct | 4 ms | 2680 KB | Output is correct |
9 | Correct | 10 ms | 2680 KB | Output is correct |
10 | Correct | 10 ms | 2676 KB | Output is correct |
11 | Correct | 9 ms | 2680 KB | Output is correct |
12 | Correct | 10 ms | 2680 KB | Output is correct |
13 | Correct | 9 ms | 2776 KB | Output is correct |
14 | Correct | 9 ms | 2808 KB | Output is correct |
15 | Correct | 9 ms | 2680 KB | Output is correct |
16 | Correct | 597 ms | 9716 KB | Output is correct |
17 | Correct | 1421 ms | 31632 KB | Output is correct |
18 | Correct | 108 ms | 5440 KB | Output is correct |
19 | Correct | 580 ms | 11236 KB | Output is correct |
20 | Correct | 1393 ms | 31812 KB | Output is correct |
21 | Correct | 820 ms | 16524 KB | Output is correct |
22 | Correct | 567 ms | 9096 KB | Output is correct |
23 | Correct | 1385 ms | 31528 KB | Output is correct |
24 | Correct | 1408 ms | 31556 KB | Output is correct |
25 | Correct | 1439 ms | 31600 KB | Output is correct |
26 | Correct | 576 ms | 11236 KB | Output is correct |
27 | Correct | 578 ms | 11272 KB | Output is correct |
28 | Correct | 579 ms | 11208 KB | Output is correct |
29 | Correct | 582 ms | 11280 KB | Output is correct |
30 | Correct | 581 ms | 11236 KB | Output is correct |
31 | Incorrect | 4 ms | 2680 KB | Output isn't correct |
32 | Halted | 0 ms | 0 KB | - |