Submission #64681

#TimeUsernameProblemLanguageResultExecution timeMemory
64681zetapiCrocodile's Underground City (IOI11_crocodile)C++14
0 / 100
25 ms23800 KiB
#include <crocodile.h> #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define ll long long #define itr ::iterator typedef pair<ll,ll> pii; const ll MAX=1e6; const ll INF=1e14; vector<pii> vec[MAX]; ll mark[MAX],dp[MAX]; int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { for(int A=0;A<M;A++) { vec[R[A][0]].pb(mp(R[A][1],L[A])); vec[R[A][1]].pb(mp(R[A][0],L[A])); } for(int A=0;A<N;A++) dp[A]=-1; priority_queue<pii,vector<pii>,greater<pii>> pq; for(int A=0;A<K;A++) { dp[P[A]]=0; pq.push(mp(0,P[A])); } while(!pq.empty()) { pii cur=pq.top(); pq.pop(); if(cur.first>dp[cur.second]) continue; for(auto A:vec[cur.second]) { if(dp[A.first]==-1) dp[A.first]=INF; else if(A.second+cur.first<dp[A.first]) { dp[A.first]=A.second+cur.first; pq.push(mp(dp[A.first],A.second+cur.first)); } } } return dp[0]; } /*signed main() { ios_base::sync_with_stdio(false); return 0; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...