# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
65008 | 2018-08-06T12:15:32 Z | zetapi | Crocodile's Underground City (IOI11_crocodile) | C++14 | 0 ms | 0 KB |
#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],mn[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++) { mn[A]=-1; dp[A]=-1; } priority_queue<pii,vector<pii>,greater<pii>> pq; for(int A=0;A<K;A++) { dp[P[A]]=0; mn[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; assert(cur.first==dp[cur].second); for(auto A:vec[cur.second]) { if(dp[A.first]==-1) { dp[A.first]=INF; mn[A.first]=cur.first+A.second; } else if(cur.first+A.second<dp[A.first]) { dp[A.first]=cur.first+A.second; if(dp[A.first]<mn[A.first]) swap(dp[A.first],mn[A.first]); pq.push(mp(dp[A.first],A.first)); } } } assert(dp[0]<INF); return (int)dp[0]; }