# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
81116 | 2018-10-23T19:50:10 Z | ToadDaveski | Evacuation plan (IZhO18_plan) | C++14 | 427 ms | 15488 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}); } } } /*for(i=1;i<=n;i++) cout<<dp[i]<<" "; return 0;*/ cin>>Q; for(i=1;i<=Q;i++) { ll x,y; cin>>x>>y; cout<<max(dp[x],dp[y])<<endl; } return 0; } /* 9 12 1 9 4 1 2 5 2 3 7 2 4 3 4 3 6 3 6 4 8 7 10 6 7 5 5 8 1 9 5 7 5 4 12 6 8 2 2 4 7 */
Compilation message
# | 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 | 4 ms | 2680 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 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 | 427 ms | 15488 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 2680 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |