Submission #195628

#	Time	Username	Problem	Language	Result	Execution time	Memory
195628		jovan_b	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1402 ms	86472 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll dist1[100005];
ll dist2[100005];
bool ext[100005];

const int MX = 1000000007;

int n;
vector <pair <int, ll>> graf[100005];
set <pair <ll, int>> q;

void sp(){

    for(int i=1; i<=n; i++){
        if(ext[i]) dist2[i] = 0;
        else dist2[i] = MX;
        dist1[i] = dist2[i];
        q.insert({dist2[i], i});
    }
    while(!q.empty()){
        int v = q.begin()->second;
        q.erase(q.begin());
        if(v == 1) return;
        for(auto pr : graf[v]){
            int c = pr.first;
            int dis = pr.second+dist2[v];
            if(dis < dist1[c]){
                q.erase({dist2[c], c});
                dist2[c] = dist1[c];
                dist1[c] = dis;
                q.insert({dist2[c], c});
            }
            else if(dis < dist2[c]){
                q.erase({dist2[c], c});
                dist2[c] = dis;
                q.insert({dist2[c], c});
            }
        }
    }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    n = N;
    int m = M;
    int k = K;
    for(int i=0; i<m; i++){
        R[i][0]++;
        R[i][1]++;
        graf[R[i][0]].push_back({R[i][1], L[i]});
        graf[R[i][1]].push_back({R[i][0], L[i]});
    }
    for(int i=0; i<k; i++){
        P[i]++;
        ext[P[i]] = 1;
    }
    sp();
    return dist2[1];
}

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