Submission #1025720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025720		idas	Crocodile's Underground City (IOI11_crocodile)	C++11	100 / 100	409 ms	71312 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first

using namespace std;
typedef pair<int, int> pii;

const int MxN=1e5+10, INF=1e9+10;
vector<pii> ad[MxN];
bool in[MxN];
int d[MxN];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    FOR(i, 0, m)
    {
        ad[r[i][0]].pb({r[i][1],l[i]});
        ad[r[i][1]].pb({r[i][0],l[i]});
    }

    FOR(i, 0, n) d[i]=-1;

    priority_queue<pii, vector<pii>, greater<pii>> q;
    FOR(i, 0, k)
    {
        q.push({0,p[i]});
        q.push({0,p[i]});
    }

    while(!q.empty()){
        int val=q.top().f, u=q.top().s; q.pop();

        if(in[u]) continue;

        if(d[u]==-1){
            d[u]=val;
            continue;
        }

        d[u]=val;
        in[u]=true;

        for(auto it : ad[u]){
            int x=it.f, w=it.s;
            if(in[x]) continue;

            int nd=min(INF, d[u]+w);
            q.push({nd,x});
        }
    }

    return d[0]==INF?-1:d[0];
}

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