#include "crocodile.h"
#include "bits/stdc++.h"
using namespace std;
struct Arista{
long long Nodo, Peso;
};
struct Arista_completa{
long long a, b, Peso;
};
struct Nodo_por_ver{
long long Distancia, Nodo, Padre;
};
bool operator<(const Arista &a, const Arista &b){
if(a.Peso < b.Peso) return 1;
if(a.Peso > b.Peso) return 0;
return a.Nodo < b.Nodo;
}
bool operator<(const Arista_completa &a, const Arista_completa &b){
if(a.Peso < b.Peso) return 1;
if(a.Peso > b.Peso) return 0;
if(a.a < b.a) return 1;
if(a.a > b.a) return 0;
return a.b < b.b;
}
bool operator<(const Nodo_por_ver &a, const Nodo_por_ver &b){
if(a.Distancia < b.Distancia) return 1;
if(a.Distancia > b.Distancia) return 0;
if(a.Nodo < b.Nodo) return 1;
if(a.Nodo > b.Nodo) return 0;
return a.Padre < b.Padre;
}
multiset<Arista_completa> Lista_de_aristas;
vector< vector<Arista> > Grafo;
vector<bool> Salidas;
vector<long long> Veloz(long long n){
vector<long long> Padres(n, -2), Distancias(n, 2222222222222222);
set<Nodo_por_ver> Cola;
Nodo_por_ver Inicio;
Inicio.Distancia = 0;
Inicio.Nodo = 0;
Inicio.Padre = 0;
Cola.insert(Inicio);
while(!Cola.empty()){
Nodo_por_ver Actual = *Cola.begin();
Cola.erase(Cola.begin());
if(Distancias[Actual.Nodo] > Actual.Distancia){
Distancias[Actual.Nodo] = Actual.Distancia;
Padres[Actual.Nodo] = Actual.Padre;
} else continue;
for(auto E: Grafo[Actual.Nodo]){
if(Distancias[E.Nodo] > Distancias[Actual.Nodo] + E.Peso){
//Distancias[E.Nodo] = Distancias[Actual.Nodo] + E.Peso;
Nodo_por_ver Siguiente;
Siguiente.Nodo = E.Nodo;
Siguiente.Distancia = Distancias[Actual.Nodo] + E.Peso;
Siguiente.Padre = Actual.Nodo;
Cola.insert(Siguiente);
}
}
}
for(long long i = 0; i < n; i++){
cout<<Distancias[i]<<" ";
}
return Padres;
}
long long Obtener_distancia(long long n){
vector<long long> Padres(n, -2), Distancias(n, 2222222222222222);
set<Nodo_por_ver> Cola;
Nodo_por_ver Inicio;
Inicio.Distancia = 0;
Inicio.Nodo = 0;
Inicio.Padre = 0;
long long Menor = 2222222222222222;
Cola.insert(Inicio);
while(!Cola.empty()){
Nodo_por_ver Actual = *Cola.begin();
Cola.erase(Cola.begin());
if(Distancias[Actual.Nodo] > Actual.Distancia){
Distancias[Actual.Nodo] = Actual.Distancia;
Padres[Actual.Nodo] = Actual.Padre;
} else continue;
for(auto E: Grafo[Actual.Nodo]){
if(Distancias[E.Nodo] > Distancias[Actual.Nodo] + E.Peso){
//Distancias[E.Nodo] = Distancias[Actual.Nodo] + E.Peso;
Nodo_por_ver Siguiente;
Siguiente.Nodo = E.Nodo;
Siguiente.Distancia = Distancias[Actual.Nodo] + E.Peso;
Siguiente.Padre = Actual.Nodo;
Cola.insert(Siguiente);
}
}
}
for(long long i = 0; i < n; i++) if(Salidas[i]) Menor = min(Menor, Distancias[i]);
return Menor;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
long long n = N, m = M;
Grafo.assign(n, {});
Salidas.assign(n, 0);
for(long long i = 0; i < m; i++){
Arista a, b;
a.Nodo = R[i][0];
b.Nodo = R[i][1];
a.Peso = L[i];
b.Peso = a.Peso;
Arista_completa _1;
_1.a = a.Nodo;
_1.b = b.Nodo;
_1.Peso = a.Peso;
Lista_de_aristas.insert(_1);
swap(_1.a, _1.b);
Lista_de_aristas.insert(_1);
Grafo[a.Nodo].push_back(b);
Grafo[b.Nodo].push_back(a);
}
/*for(long long i = 0; i < K; i++) Salidas[P[i]] = 1;
vector<long long> Padres = Veloz(n);
Grafo.assign(n, {});
for(long long i = 0; i < n; i++){
Arista_completa _1;
_1.a = i;
_1.b = Padres[i];
_1.Peso = -2;
Arista a, b;
a.Nodo = i;
b.Nodo = Padres[i];
a.Peso = (*Lista_de_aristas.lower_bound(_1)).Peso;
b.Peso = a.Peso;
Grafo[a.Nodo].push_back(b);
Grafo[b.Nodo].push_back(a);*/
/*Arista_completa a;
a.a = i;
a.b = Padres[i];
a.Peso = -2;
a.Peso = (*Lista_de_aristas.lower_bound(a)).Peso;
Lista_de_aristas.erase(a);
swap(a.a, a.b);
Lista_de_aristas.erase(a);*/
//}
vector<long long> Distancias(n, 2222222222222222);
deque<long long> Cola = {0};
Distancias[0] = 0;
int r = 0;
while(!Cola.empty()){
long long Nodo = Cola[0];
Cola.pop_front();
for(auto E: Grafo[Nodo]){
if(Distancias[E.Nodo] > Distancias[Nodo] + E.Peso){
Distancias[E.Nodo] = Distancias[Nodo] + E.Peso;
r = max(r, (int)(Distancias[Nodo] + E.Peso));
Cola.push_back(E.Nodo);
}
}
}
/*for(auto E: Lista_de_aristas){
Arista a, b;
a.Nodo = E.a;
b.Nodo = E.b;
a.Peso = E.Peso;
b.Peso = E.Peso;
Grafo[a.Nodo].push_back(b);
Grafo[b.Nodo].push_back(a);
}*/
return r;
}
