# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
367606 | 2021-02-17T18:15:20 Z | Iwanttobreakfree | Crocodile's Underground City (IOI11_crocodile) | C++ | 0 ms | 0 KB |
#include "crocodile.h" #include <iostream> #include <vector> #include <queue> using namespace std; long long int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){ vector<long long int> distancia(N,1e9); long long int maximo=0; vector<vector<pair<long long int,long long int> > > conexiones(N,vector<pair<long long int,long long int> >()); for(long long int i=0;i<M;i++){ conexiones[R[i][0]].push_back(make_pair(L[i],R[i][1])); conexiones[R[i][1]].push_back(make_pair(L[i],R[i][0])); } priority_queue <pair<long long int,long long int> > q; q.push(make_pair(0,0)); distancia[0]=0; long long int nodo,coste; while(!q.empty()){ nodo=q.top().second; coste=-q.top().first; q.pop(); if(coste>distancia[nodo])continue; for(pair<long long int,long long int> con:conexiones[nodo]){ long long int arista=-con.first; long long int siguiente=con.second; if(distancia[siguiente]>distancia[nodo]+arista){ distancia[siguiente]=distancia[nodo]+arista; q.push(make_pair(-arista,siguiente)); } } } for(long long int i=0;i<K;i++){ maximo=max(maximo,distancia[P[i]]); } return maximo; }