Submission #1219850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219850		Octa_pe_info	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	268 ms	49568 KiB

crocodile

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

struct arbore{

    int nod,cost;

    bool operator>(const arbore & o)const{

        return cost > o.cost;
    }
};

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

    vector<vector<arbore>>tabel(N+1);
    vector<vector<int>>dp(N+1,vector<int>(2,1e9+1));

    for(int i=0;i<M;i++){

        tabel[R[i][0]].push_back({R[i][1],L[i]});
        tabel[R[i][1]].push_back({R[i][0],L[i]});
    }

    priority_queue<arbore,vector<arbore>,greater<arbore>>pq;

    for(int i=0;i<K;i++){

        pq.push({P[i],0});
        dp[P[i]] = {0,0};
    }

    while(!pq.empty()){

        auto curent = pq.top();
        pq.pop();

        if(dp[curent.nod][1] < curent.cost)
            continue;

        for(auto i : tabel[curent.nod]){

            if(curent.cost + i.cost < dp[i.nod][0]){

                if(dp[i.nod][0] < dp[i.nod][1])
                    pq.push({i.nod,dp[i.nod][0]});///practic am mai gasit unu bun

                dp[i.nod][1] = dp[i.nod][0];
                dp[i.nod][0] = curent.cost + i.cost;
            }
            else
                if(curent.cost + i.cost < dp[i.nod][1]){

                    dp[i.nod][1] = curent.cost + i.cost;
                    pq.push({i.nod,dp[i.nod][1]});
                }
        }
    }

    return dp[0][1];
}

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