Submission #440617

#	Time	Username	Problem	Language	Result	Execution time	Memory
440617		julian33	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	603 ms	63604 KiB

crocodile

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int mxN=1e5+5,inf=1e9+10;

vector<pii> graph[mxN];

int dist[mxN][2],seen[mxN],n,m,k,a,b,w;

priority_queue<pii,vector<pii>, greater<pii> > q;

int travel_plan(int N, int M, int R[][2], int W[], int K, int E[]){
    int n=N;
    int m=M;
    int k=K;

    for(int i=0;i<n;i++) 
        dist[i][0]=dist[i][1]=inf;
    for(int i=0;i<m;i++){
        graph[R[i][0]].push_back(pii(R[i][1],W[i]));
        graph[R[i][1]].push_back(pii(R[i][0],W[i]));
    }
    for(int i=0;i<k;i++){
        q.push(pii(0,E[i]));
        dist[E[i]][1]=0;
    }
    while(!q.empty()){
        int at=q.top().second;
        q.pop();
        if(seen[at]) continue;
        seen[at]=true;
        for(pii &i:graph[at]){
            if(dist[at][1]+i.second < dist[i.first][1]){
                dist[i.first][1]=dist[at][1]+i.second;
                if(dist[i.first][1]<dist[i.first][0]) swap(dist[i.first][1],dist[i.first][0]);
                q.push(pii(dist[i.first][1],i.first));
            }
        }
    }
    return dist[0][1];
}

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