# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
226102 | 2020-04-22T14:26:10 Z | cfalas | Crocodile's Underground City (IOI11_crocodile) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> using namespace std; #include "crocodile.h" #define F first #define S second typedef pair<int, int> ii; typedef vector<ii> vii; vector<vii> adj; #define INF 1500000000 map<int, bool> child[1000000]; int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) { adj.assign(n+1, vii()); for(int i=0;i<m;i++){ adj[r[i][0]].push_back(ii(l[i], r[i][1])); adj[r[i][1]].push_back(ii(l[i], r[i][0])); } priority_queue<ii> q; for(int i=0;i<n;i++) dist[i]=INF; int cnt[n+1] = {}, ans=0; for(int i=0;i<k;i++){ q.push(ii(0,p[i])); q.push(ii(0,p[i])); dist[p[i]] = 0; } while(!q.empty()){ ii t = q.top(); q.pop(); cnt[t.S]++; if(cnt[t.S]!=2) continue; if(t.S==0) ans=-t.F; for(auto v : adj[t.S]){ q.push(ii(t.F-v.F, v.S)); } } return ans; }