Submission #228379

#TimeUsernameProblemLanguageResultExecution timeMemory
228379tushar_2658Crocodile's Underground City (IOI11_crocodile)C++14
100 / 100
720 ms93412 KiB
#include "crocodile.h" #include "bits/stdc++.h" using namespace std; const int maxn = 100005; using ll = long long; vector<pair<int, ll>> edges[maxn]; ll dis[maxn][2]; bool vis[maxn]; int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { for(int i = 0; i < M; ++i){ edges[R[i][0]].push_back(make_pair(R[i][1], L[i])); edges[R[i][1]].push_back(make_pair(R[i][0], L[i])); } using pii = pair<ll, int>; priority_queue<pii, vector<pii>, greater<pii>> pq; memset(dis, 63, sizeof dis); for(int i = 0; i < K; ++i){ pq.push(make_pair(0, P[i])); dis[P[i]][0] = dis[P[i]][1] = 0; } while(!pq.empty()){ pii s = pq.top(); pq.pop(); if(vis[s.second])continue; vis[s.second] = 1; for(auto i : edges[s.second]){ ll cost = dis[s.second][1] + i.second; if(dis[i.first][0] >= cost){ dis[i.first][1] = dis[i.first][0]; dis[i.first][0] = cost; pq.push(make_pair(dis[i.first][1], i.first)); }else if(dis[i.first][1] > cost){ dis[i.first][1] = cost; pq.push(make_pair(dis[i.first][1], i.first)); } } } return dis[0][1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...