#include "crocodile.h"
#include <functional>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 2E9;
struct chamber {
int num;
bool completed = false;
bool is_exit = false;
vector<pair<int,int>> others;
ll wc = INF, bc = INF;
void update_others(vector<chamber>& chambers, priority_queue<chamber, vector<chamber>, greater<>>& current_exits) {
if (num == 0) return;
completed = true;
for (auto [child, cost] : others) {
// cout << "visiting " << child << " from " << num << "\n";
if (chambers[child].completed) continue;
if (chambers[child].update_cases(wc+cost)) {
current_exits.push(chambers[child]);
}
}
}
bool update_cases(ll val) {
if (wc == INF) {
wc = val;
if (wc < bc) swap(wc,bc);
return (wc != INF);
}
if (val >= wc) return false;
wc = val;
if (wc < bc) swap(wc,bc);
return true;
}
bool operator<(const chamber& other_chamber) const {
return wc < other_chamber.wc;
}
bool operator>(const chamber& other_chamber) const {
return wc > other_chamber.wc;
}
};
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
vector<chamber> chambers(N);
priority_queue<chamber, vector<chamber>, greater<>> current_exits;
for (int i = 0; i < N; i++) {
chambers[i].num = i;
}
for (int i = 0; i < M; i++) {
int a = R[i][0];
int b = R[i][1];
chambers[a].others.emplace_back(b, L[i]);
chambers[b].others.emplace_back(a, L[i]);
}
for (int i = 0; i < K; i++) {
chambers[P[i]].is_exit = true;
chambers[P[i]].completed = true;
chambers[P[i]].wc = 0;
chambers[P[i]].bc = 0;
current_exits.push(chambers[P[i]]);
}
while (!current_exits.empty()) {
int currentChamber = current_exits.top().num; current_exits.pop();
// cout << "visited " << currentChamber << "\n";
chambers[currentChamber].update_others(chambers, current_exits);
}
return chambers[0].wc;
}
