Submission #18649

#TimeUsernameProblemLanguageResultExecution timeMemory
18649ggohCrocodile's Underground City (IOI11_crocodile)C++98
100 / 100
684 ms181496 KiB
#include "crocodile.h" #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<queue> int a,b,c; long long D[100003][2]; struct A{ int to;long long cost; }; std::vector<A>G[100003]; struct B{ int pos;long long min; }; std::priority_queue<B>PQ; bool operator<(B aa,B bb){return aa.min>bb.min;} int travel_plan(int N,int M,int R[][2],int L[],int K,int P[]) { a=N; b=M; c=K; for(int i=0;i<b;i++) { G[R[i][0]].push_back({R[i][1],(long long)L[i]}); G[R[i][1]].push_back({R[i][0],(long long)L[i]}); } long long X=1e9; int u;long long l; for(int i=0;i<a;i++)D[i][0]=D[i][1]=X*X; for(int i=0;i<c;i++)D[P[i]][0]=D[P[i]][1]=0; for(int i=0;i<c;i++) { for(int j=0;j<G[P[i]].size();j++) { u=G[P[i]][j].to;l=G[P[i]][j].cost; if(D[u][0]>l) { if(D[u][1]!=D[u][0])PQ.push({u,D[u][0]}); D[u][1]=D[u][0]; D[u][0]=l; } else if(D[u][1]>l) { D[u][1]=l; PQ.push({u,D[u][1]}); } } } while(!PQ.empty()) { B o=PQ.top();PQ.pop(); if(D[o.pos][1]!=o.min)continue; for(int i=0;i<G[o.pos].size();i++) { u=G[o.pos][i].to;l=G[o.pos][i].cost; if(D[u][0]>l+o.min) { if(D[u][1]!=D[u][0])PQ.push({u,D[u][0]}); D[u][1]=D[u][0]; D[u][0]=l+o.min; } else if(D[u][1]>l+o.min) { D[u][1]=l+o.min; PQ.push({u,D[u][1]}); } } } return (int)D[0][1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...