Submission #7699

#	Time	Username	Problem	Language	Result	Execution time	Memory
7699		baneling100	Crocodile's Underground City (IOI11_crocodile)	C++98	100 / 100	640 ms	152568 KiB

crocodile

#include "crocodile.h"
#include <algorithm>
#include <vector>
#include <queue>
#define INF 0x7fffffff

using namespace std;

typedef pair <int,int> ppair;
static priority_queue <ppair,vector<ppair>,greater<ppair> > Q;
static vector <ppair> A[100000];
static int D[100000][2], Check[100000];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {

    int i, j, Now;

    for(i=0 ; i<M ; i++) {
        A[R[i][0]].push_back(make_pair(R[i][1],L[i]));
        A[R[i][1]].push_back(make_pair(R[i][0],L[i]));
    }
    for(i=0 ; i<N ; i++)
        D[i][0]=D[i][1]=INF;
    for(i=0 ; i<K ; i++) {
        D[P[i]][0]=D[P[i]][1]=0;
        Q.push(make_pair(0,P[i]));
    }
    while(!Q.empty()) {
        Now=Q.top().second;
        Q.pop();
        if(Check[Now])
            continue;
        Check[Now]=1;
        j=A[Now].size();
        for(i=0 ; i<j ; i++)
            if(!Check[A[Now][i].first]) {
                if(D[A[Now][i].first][0]>D[Now][1]+A[Now][i].second) {
                    D[A[Now][i].first][1]=D[A[Now][i].first][0];
                    D[A[Now][i].first][0]=D[Now][1]+A[Now][i].second;
                    if(D[A[Now][i].first][1]!=INF)
                        Q.push(make_pair(D[A[Now][i].first][1],A[Now][i].first));
                }
                else if(D[A[Now][i].first][1]>D[Now][1]+A[Now][i].second) {
                    D[A[Now][i].first][1]=D[Now][1]+A[Now][i].second;
                    Q.push(make_pair(D[A[Now][i].first][1],A[Now][i].first));
                }
            }
    }
    return D[0][1];
}

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