# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
237083 | Autoratch | Crocodile's Underground City (IOI11_crocodile) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<long long,int>
const int N = 1e5 + 1;
vector<pair<int,int> > adj[N];
vector<int> ep;
priority_queue<pii,vector<pii>,greater<pii> > q;
long long dist[N];
bool visited[N];
long long dfs(int u)
{
if(dist[u]==0) return 0;
long long mn = LLONG_MAX,mn2 = LLONG_MAX;
int m,m2;
for(auto [d,v] : adj[u]) if(dist[v]<dist[u])
{
long long each = dfs(v)+d;
if(each<mn) mn2 = mn,m2 = m,mn = each,m = v;
else if(each<mn2) mn2 = each,m2 = v;
}
return mn2;
}
long long travel_plan(int n,int m,int r[][2],int l[],int k,int p[])
{
for(int i = 0;i < m;i++)
{
int a = r[i][0],b = r[i][1],d = l[i];
adj[a].push_back({d,b});
adj[b].push_back({d,a});
}
for(int i = 0;i < k;i++) ep.push_back(p[i]);
for(int i = 0;i < n;i++) dist[i] = LLONG_MAX;
for(int x : ep) dist[x] = 0,q.push({0,x});
while(!q.empty())
{
int u = q.top().second;
q.pop();
for(auto [d,v] : adj[u]) if(dist[u]+d<dist[v]) dist[v] = dist[u]+d,q.push({dist[v],v});
}
return dfs(0);
}