Submission #1126057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126057		ardadut	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	1 ms	584 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;

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

    return dist[0].second;

}

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