#include "crocodile.h"
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 1e15; // Sufficiently large for the constraints
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
// 1. Setup Adjacency List
vector<vector<pair<int, int>>> adj(N);
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]});
}
// 2. Initialize Distance Arrays
// best_dist: The absolute shortest path to an exit (which the crocodile will block)
// second_dist: The second shortest path (the one we are actually forced to take)
vector<ll> best_dist(N, INF);
vector<ll> second_dist(N, INF);
// Priority Queue stores {distance, node_index}
// Using greater<> makes it a min-priority queue
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
// 3. Initialize Exits
for (int i = 0; i < K; i++) {
int exit_node = P[i];
best_dist[exit_node] = 0;
second_dist[exit_node] = 0;
pq.push({0, exit_node});
}
// 4. Modified Dijkstra
while (!pq.empty()) {
ll d = pq.top().first;
int u = pq.top().second;
pq.pop();
// If we've already found a better second-best path for this node, skip it
if (d > second_dist[u]) continue;
for (auto& edge : adj[u]) {
int v = edge.first;
ll weight = edge.second;
ll new_path = d + weight;
if (new_path < best_dist[v]) {
// The old best becomes the new second-best
second_dist[v] = best_dist[v];
best_dist[v] = new_path;
// Only push to PQ if we have a valid second-best path
if (second_dist[v] != INF) {
pq.push({second_dist[v], v});
}
} else if (new_path < second_dist[v]) {
// This path is better than our current second-best
second_dist[v] = new_path;
pq.push({second_dist[v], v});
}
}
}
return (int)second_dist[0];
}
