Submission #1090709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090709		AlgorithmWarrior	Crocodile's Underground City (IOI11_crocodile)	C++14	89 / 100	264 ms	129828 KiB

crocodile

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

using namespace std;

int N,M,K;
struct edge
{
    int nod;
    int 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;
int dist1[MAX],dist2[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]=1e9+100000000;
    while(K--)
    {
        int nod;
        nod=P[K];
        ++nod;
        dist1[nod]=dist2[nod]=0;
        pq.push({nod,0});
    }
}

void djikstra()
{
    while(!pq.empty() && pq.top().nod!=1)
    {
        int nod=pq.top().nod;
        int len=pq.top().len;
        pq.pop();
        if(len>dist2[nod])
            continue;
        for(auto per : G[nod])
        {
            int nod2=per.nod;
            int len2=per.len;
            if(dist2[nod2]>len+len2)
            {
                if(dist1[nod2]>len+len2)
                {
                    dist2[nod2]=dist1[nod2];
                    dist1[nod2]=len+len2;
                }
                else
                    dist2[nod2]=len+len2;
                if(dist2[nod2]<=1e9)
                    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: 0 / 11