#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
std::vector<std::vector<std::pair<int,ll>>> adj;
int block[100100];
ll pot[100100];
//what best block would currently be, dist without that block
int go[100100];
ll dist[100100];
//what do dist go to with optimal block, dist from the exit
bool inQueue[100100];
//idk if i need this because queue will be push a lot
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
std::priority_queue<std::pair<int,int>> pq;
//what dist we could get,node
adj.resize(N+10);
for(int i=0;i<M;i++){
adj[R[i][0]].push_back({R[i][1],L[i]});
adj[R[i][1]].push_back({R[i][0],L[i]});
}
for(int i=0;i<N;i++){
dist[i]=1e18;
pot[i]=1e18;
go[i]=-1;
block[i]=-1;
}
for(int i=0;i<K;i++){
dist[P[i]]=0;
pot[P[i]]=0;
pq.push({-dist[P[i]],P[i]});
}
while(!pq.empty()){
int curr = pq.top().second;
int cdist = -pq.top().first;
pq.pop();
for(auto [to,weight]:adj[curr]){
if(curr==block[to]){
pot[to]=std::min((ll)1e18,pot[to]);
continue;
}
else if(cdist+weight>=dist[to])continue;
//catch bad path
if(block[to]==-1){
//block was empty
pot[to]=cdist+weight;
block[to]=curr;
}
else if(cdist+weight<pot[to]){
//new optimal path
//push old optimal path to second best
go[to]=block[to];
dist[to]=pot[to];
pot[to]=cdist+weight;
block[to]=curr;
}
else if(cdist+weight<dist[to]){
//new optimal unblocked path(2nd best)
dist[to]=cdist+weight;
go[to]=curr;
}
else continue; //if nothing is worth calculating dont push the priortiy queue i do think if condition at the top will already catch it;
if(dist[to]<1e18){
pq.push({-dist[to],to});
}
}
}
return dist[0];
}
/*
5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1
3
4
7
*/
/*
5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1
3
14
*/
