Submission #1126151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126151		ardadut	Crocodile's Underground City (IOI11_crocodile)	C++20	89 / 100	495 ms	77116 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
#define ll long long
#define pb push_back
#define endl "\n"
#define vec vector<ll>
#define vecvec vector<vector<ll>>
    
using namespace std;
    
/*#define FileName ""
string Ghhhh = ".in";
string Ghhhhh = ".out";
ifstream Girdi(FileName + Ghhhh);
ofstream Cikti(FileName + Ghhhhh);
#define cin Girdi
#define cout */

const ll INF = 1e15;

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

    vector<vector<pair<ll,ll>>> adj(N+1);

    for(ll i = 0 ; i < M ; i++){
        adj[R[i][0]].pb({R[i][1],L[i]});
        adj[R[i][1]].pb({R[i][0],L[i]});
    }

    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
    vector<pair<ll,ll>> dist(N+1);

    for(ll i = 0 ; i < N ; i++){
        dist[i] = {INF,INF};
    }

    for(ll i = 0 ; i < K ; i++){
        pq.push({0,P[i]}); 
        dist[P[i]] = {0,0};
    }

    while(!pq.empty()){
        ll node = pq.top().second;
        ll weight = pq.top().first;
        pq.pop();

        if(weight > dist[node].second) continue;

        for(auto go : adj[node]){
            if(weight + go.second < dist[go.first].first){
                dist[go.first] = {weight + go.second,dist[go.first].first};
                pq.push({dist[go.first].second,go.first});
            }else if(weight + go.second < dist[go.first].second){
                dist[go.first].second = weight + go.second;
                pq.push({dist[go.first].second,go.first});
            } 
        }

    }

    return dist[0].second;

}

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