#include "crocodile.h"
#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
vector<int> distancia(N,1e9);
int maximo=1e9;
bool primero;
vector<vector<pair<int,int> > > conexiones(N,vector<pair<int,int> >());
set <int> salidas;
for(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]));
}
for(int i=0;i<K;i++)salidas.insert(P[i]);
priority_queue <pair<int,int> > q;
q.push(make_pair(0,0));
distancia[0]=0;
priority_queue <pair<int,int> >posibles;
priority_queue <pair<int,int> >caminos;
int nodo,coste;
while(!q.empty()){
nodo=q.top().second;
coste=-q.top().first;
q.pop();
for(pair<int,int> con:conexiones[nodo]){
int arista=con.first;
int siguiente=con.second;
if(salidas.find(siguiente)!=salidas.end())posibles.push(make_pair(-arista,siguiente));
else caminos.push(make_pair(-arista,siguiente));
}
primero=true;
if(posibles.empty()){
while(!caminos.empty()){
if(primero)primero=false;
else if(distancia[caminos.top().first]>distancia[nodo]+caminos.top().second){
distancia[caminos.top().first]=distancia[nodo]+caminos.top().second;
q.push(make_pair(caminos.top().first,caminos.top().second));
}
caminos.pop();
}
}
else{
while(!posibles.empty()){
if(primero)primero=false;
else if(distancia[posibles.top().first]>distancia[nodo]+posibles.top().second){
distancia[posibles.top().first]=distancia[nodo]+posibles.top().second;
q.push(make_pair(posibles.top().first,posibles.top().second));
}
posibles.pop();
while(!caminos.empty()){
if(distancia[caminos.top().first]>distancia[nodo]+caminos.top().second){
distancia[caminos.top().first]=distancia[nodo]+caminos.top().second;
q.push(make_pair(caminos.top().first,caminos.top().second));
}
caminos.pop();
}
}
}
}
for(int i=0;i<K;i++){
maximo=min(maximo,distancia[P[i]]);
}
return maximo;
}
Compilation message
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:24:11: warning: variable 'coste' set but not used [-Wunused-but-set-variable]
24 | int nodo,coste;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
