Submission #18423

#	Time	Username	Problem	Language	Result	Execution time	Memory
18423		tlwpdus	Crocodile's Underground City (IOI11_crocodile)	C++98	100 / 100	697 ms	187744 KiB

crocodile

#include "crocodile.h"
#include<vector>
#include<queue>
#include<stdio.h>

using namespace std;

typedef long long ll;

struct edge {
    int j;
    ll w;
    edge(int j, ll w):j(j),w(w){}
    edge(){}
};

struct dijk {
    int loc;
    ll w;
    dijk(int l, ll w):loc(l),w(w){}
    dijk(){}
    inline bool operator < (const dijk &A) const {return w>A.w;}
};

vector<edge> lis[100100];
priority_queue<dijk> pq;
ll dist[100100][2];
bool visit[100100];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    int i;
    for (i=0;i<N;i++) dist[i][0] = dist[i][1] = 1LL<<60;
    for (i=0;i<M;i++) {
        lis[R[i][0]].push_back(edge(R[i][1],L[i]));
        lis[R[i][1]].push_back(edge(R[i][0],L[i]));
    }
    for (i=0;i<K;i++) {
        pq.push(dijk(P[i],0));
        dist[P[i]][0] = dist[P[i]][1] = 0;
    }
    while(!pq.empty()) {
        dijk tmp = pq.top();
        pq.pop();
        int here = tmp.loc;
        if (visit[here]) continue;
        if (dist[here][1]!=tmp.w) continue;
        visit[here] = true;
        for (i=0;i<lis[here].size();i++) {
            int there = lis[here][i].j;
            int w = lis[here][i].w;
            if (visit[there]) continue;
            if (dist[there][0]>w+tmp.w) {
                dist[there][1] = dist[there][0];
                dist[there][0] = w+tmp.w;
                pq.push(dijk(there,dist[there][1]));
            }
            else if (dist[there][1]>w+tmp.w) {
                dist[there][1] = w+tmp.w;
                pq.push(dijk(there,dist[there][1]));
            }
        }
    }
    return dist[0][1];
}

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