Submission #724915

#	Time	Username	Problem	Language	Result	Execution time	Memory
724915		sofija6	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	489 ms	62096 KiB

crocodile

#include <bits/stdc++.h>
#define ll int
#define MAXN 100010
#define llinf 1e9
using namespace std;
vector<pair<ll,ll> > G[MAXN];
pair<ll,ll> t[MAXN];
void Dijkstra(ll N,ll K,ll P[])
{
    for (ll i=0;i<N;i++)
        t[i]={llinf,llinf};
    priority_queue<pair<ll,pair<ll,ll> >,vector<pair<ll,pair<ll,ll> > >,greater<pair<ll,pair<ll,ll> > > > q;
    for (ll i=0;i<K;i++)
    {
        t[P[i]]={0,0};
        q.push({0,{0,P[i]}});
    }
    while (!q.empty())
    {
        ll min2=q.top().first,min1=q.top().second.first,u=q.top().second.second;
        q.pop();
        if (t[u].first!=min2 || t[u].second!=min1)
            continue;
        for (auto next : G[u])
        {
            ll v=next.first,w=next.second;
            if (t[v].second>t[u].first+w)
            {
                swap(t[v].first,t[v].second);
                t[v].second=t[u].first+w;
                if (t[v].first!=llinf)
                    q.push({t[v].first,{t[v].second,v}});
                continue;
            }
            if (t[v].first>t[u].first+w)
            {
                t[v].first=t[u].first+w;
                q.push({t[v].first,{t[v].second,v}});
            }
        }
    }
}
ll travel_plan(ll N,ll M,ll R[][2],ll L[],ll K,ll P[])
{
    for (ll i=0;i<M;i++)
    {
        G[R[i][0]].push_back({R[i][1],L[i]});
        G[R[i][1]].push_back({R[i][0],L[i]});
    }
    Dijkstra(N,K,P);
    return (t[0].first==llinf?-1 : t[0].first);
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11