Submission #1152998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152998		AlgorithmWarrior	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	436 ms	141672 KiB

crocodile

#include <bits/stdc++.h>
#define MAX 3000005

using namespace std;

int N,M,K;
struct edge
{
    int nod;
    long long len;
};
class cmp
{
public:
    bool operator()(edge a,edge b)
    {
        return a.len>b.len;
    }
};
vector<edge>G[MAX];
priority_queue<edge,vector<edge>,cmp>pq;
long long dist1[MAX],dist2[MAX];
int node1[MAX],node2[MAX];

void read(int N,int M,int R[][2],int L[],int K,int P[])
{
    while(M--)
    {
        int nod1,nod2,len;
        nod1=R[M][0];
        nod2=R[M][1];
        len=L[M];
        ++nod1;
        ++nod2;
        G[nod1].push_back({nod2,len});
        G[nod2].push_back({nod1,len});
    }
    int i;
    for(i=1;i<=N;++i)
        dist1[i]=dist2[i]=1e18;
    while(K--)
    {
        int nod;
        nod=P[K];
        ++nod;
        dist1[nod]=dist2[nod]=0;
        pq.push({nod,0});
    }
}

void djikstra()
{
    while(!pq.empty())
    {
        int nod=pq.top().nod;
        long long len=pq.top().len;
        pq.pop();
        if(len>dist2[nod])
            continue;
        for(auto per : G[nod])
        {
            int nod2=per.nod;
            long long len2=per.len;
            if(dist2[nod2]>len+len2)
            {
                if(dist1[nod2]>len+len2)
                {
                    if(node1[nod2]!=nod){
                    dist2[nod2]=dist1[nod2];
                    dist1[nod2]=len+len2;
                    node2[nod2]=node1[nod2];
                    node1[nod2]=nod;
                    if(dist2[nod2]<1e18)
                    pq.push({nod2,dist2[nod2]});
                    }
                    else{
                    dist1[nod2]=len+len2;
                    node1[nod2]=nod;
                    }
                }
                else
                if(node1[nod2]!=nod){
                    dist2[nod2]=len+len2;
                    node2[nod2]=nod;
                    if(dist2[nod2]<1e18)
                    pq.push({nod2,dist2[nod2]});
                }
            }
        }
    }
}

int travel_plan(int N,int M,int R[][2],int L[],int K,int P[])
{
    read(N,M,R,L,K,P);
    djikstra();
    return dist2[1];
}

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