Submission #598405

#TimeUsernameProblemLanguageResultExecution timeMemory
598405dariaCrocodile's Underground City (IOI11_crocodile)C++14
100 / 100
485 ms63156 KiB
#include "crocodile.h" #include "bits/stdc++.h" using namespace std; #define f first #define s second const int INF = 1000000005; int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){ // return -1; vector<pair<int, int> > adj[n]; for(int i=0; i<m; ++i){ adj[r[i][1]].push_back({r[i][0], l[i]}); adj[r[i][0]].push_back({r[i][1], l[i]}); } vector<pair<int, int> > d(n, {INF, INF}); vector<bool> vis(n, 0); priority_queue<pair<int, int> > pq; for(int i=0; i<k; ++i){ d[p[i]].f = d[p[i]].s = 0; pq.push({0, p[i]}); } while(!pq.empty()){ /*for(int i=0; i<n; ++i) cout << d[i].f << " " << d[i].s << endl; cout << endl;*/ int a = pq.top().s; pq.pop(); if(vis[a]) continue; vis[a] = 1; for(auto P : adj[a]){ int b = P.f, w = P.s; if(d[a].s + w <= d[b].f){ d[b].s = d[b].f; d[b].f = d[a].s + w; pq.push({-d[b].s, b}); } else if(d[a].s + w < d[b].s){ d[b].s = d[a].s + w; pq.push({-d[b].s, b}); } } } //cout << d[0].s << endl; if(d[0].s == INF) return -1; return d[0].s; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...