Submission #426206

#	Time	Username	Problem	Language	Result	Execution time	Memory
426206		chirathnirodha	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	665 ms	73012 KiB

crocodile

//Coded by Chirath Nirodha
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define P push
typedef long long ll;
 
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
  vector<pair<ll,ll> > adj[N];
  for(int i=0;i<M;i++){
    adj[R[i][0]].PB(MP(R[i][1],L[i]));
    adj[R[i][1]].PB(MP(R[i][0],L[i]));
  }
  ll shortest[N][2];
  for(int i=0;i<N;i++){
    shortest[i][0]=10000000000000000;
    shortest[i][1]=10000000000000000;
  }
  priority_queue<pair<ll,ll> > q;
  for(int i=0;i<K;i++){
    shortest[P[i]][0]=0;
    shortest[P[i]][1]=0;
    q.P(MP(0,P[i]));
  }
  while(!q.empty()){
    int c=q.top().S;
    ll val=-q.top().F;
    q.pop();
    if(val>shortest[c][1])continue;
    for(int i=0;i<adj[c].size();i++){
      int a=adj[c][i].F;
      ll len=adj[c][i].S;
	  ll pre=shortest[a][1];
      if(shortest[a][0]>val+len){
        shortest[a][1]=shortest[a][0];
        shortest[a][0]=val+len;
      }
      else if(shortest[a][1]>val+len)shortest[a][1]=val+len;
	  
	  if(shortest[a][1]<pre)q.P(MP(-shortest[a][1],a));
    }
  }
  int ans=shortest[0][1];
  return ans;
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<adj[c].size();i++){
      |                 ~^~~~~~~~~~~~~~

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