Submission #241041

#	Time	Username	Problem	Language	Result	Execution time	Memory
241041		lakshith_	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	695 ms	61424 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
#define pb push_back
 
using namespace std;
 
vector<vector<pair<int,int>>> adjList(100000,vector<pair<int,int>>());
vector<pair<int,int>> dist(100000); 

int travel_plan(int n,int m,int r[][2],int l[],int k,int p[]){
  for(int i=0;i<m;i++){
    adjList.at(r[i][0]).pb({r[i][1],l[i]});
    adjList.at(r[i][1]).pb({r[i][0],l[i]});
  }
  //dijsktra
  priority_queue< pair<int,int>, vector<pair<int,int>> , greater<pair<int,int>>> pq;
  for(int i=0;i<n;i++)
    dist.at(i) = {INT_MAX,INT_MAX};
  for(int i=0;i<k;i++){
    pq.push({0,p[i]});
    dist.at(p[i]) = {0,0};
  }
  
  while(!pq.empty()){
    int cost = pq.top().first;
    int node = pq.top().second;
    pq.pop();
    if(cost > dist[node].second)continue;
    for(pair<int,int> v : adjList.at(node)){
      int to = v.first;
      int nCost = cost + v.second;
      int prv = dist[to].second;
      if(nCost<dist[to].first)
        dist[to].second = dist[to].first,dist[to].first=nCost;
      else if(nCost<dist[to].second)
        dist[to].second = nCost;
      if(dist[to].second<prv)
        pq.push({dist[to].second,to});
    }
  }
  return dist[0].second;
}

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