Submission #896513

#	Time	Username	Problem	Language	Result	Execution time	Memory
896513		anton	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	496 ms	69424 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>

vector<vector<pii>> adj;
vector<bool> vis;
vector<int> dist;

const int INF = 1e9 +2;


int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  adj.resize(N);
  vis.resize(N);
  dist.resize(N, INF);

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

  priority_queue<pii> pq;

  for(int i = 0; i<K; i++){
    pq.push(pii(0, P[i]));
    vis[P[i]] =true;
  }

  while(pq.size()>0){
    auto cur = pq.top();
    pq.pop();
    int cur_id = cur.second;
    int cur_dist = -cur.first;

    //cout<<cur_id<<" "<<cur_dist<<endl;
    if(!vis[cur_id]){
      vis[cur_id] = true;
    }
    else{
      if(dist[cur_id]>cur_dist){
        dist[cur_id] = cur_dist;
        for(auto e: adj[cur_id]){
          if(dist[e.first]>cur_dist + e.second){
            pq.push(pii(-cur_dist - e.second, e.first));
          }
        }
      }

    }
  }

  return(dist[0]);
}

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