Submission #1275875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275875		k12_khoi	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	299 ms	44916 KiB

crocodile

#include "crocodile.h"

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int MAXN=1e5+5;
const int MMM=1e6+5;
const int oo=1e9+1;

int N,M,K,dist,u,x,y,z;
int R[MMM][2],L[MMM],P[MAXN],d[MAXN][2];
vector <pii> adj[MAXN];
priority_queue <pii,vector<pii>,greater<pii>> pq;

int travel_plan(int N,int M,int R[][2],int L[],int K,int P[])
{
    auto dijkstra = [&](int goal)
    {
        while (!pq.empty()) pq.pop();

        for (int i=0;i<N;i++)
        d[i][0]=d[i][1]=oo;

        for (int i=0;i<K;i++)
        {
            d[P[i]][0]=d[P[i]][1]=0;
            pq.push(make_pair(0,P[i]));
        }

        while (!pq.empty())
        {
            dist=pq.top().X;
            u=pq.top().Y;
            pq.pop();

            if (dist>d[u][1]) continue;

            if (u==goal) return dist;

            for (pii v:adj[u])
            if (d[v.Y][0]>dist+v.X)
            {
                if (d[v.Y][1]!=d[v.Y][0])
                {
                    d[v.Y][1]=d[v.Y][0];
                    pq.push(make_pair(d[v.Y][1],v.Y));
                }

                d[v.Y][0]=dist+v.X;
            }
            else if (d[v.Y][1]>dist+v.X)
            {
                d[v.Y][1]=dist+v.X;
                pq.push(make_pair(d[v.Y][1],v.Y));
            }
        }

        return d[goal][1];
    };

    for (int i=0;i<M;i++)
    {
        x=R[i][0];
        y=R[i][1];
        z=L[i];

        adj[x].push_back(make_pair(z,y));
        adj[y].push_back(make_pair(z,x));
    }

    return dijkstra(0);
}

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