#include "crocodile.h"
#include <tuple>
#include <utility>
#include <iostream>
#include <queue>
#include <vector>
using i64 = int64_t;
struct Node {
i64 dist;
i64 index;
bool operator<(const Node &rhs) const {
return std::tie(rhs.dist, index) < std::tie(dist, rhs.index);
}
};
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
std::vector<std::vector<std::pair<i64, i64>>> adj(N);
for (i64 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]});
}
std::vector<i64> distances(N, 1e18);
std::vector<i64> distances2(N, 1e18);
std::priority_queue<Node> pq;
for (i64 i = 0; i < K; i++) {
distances[P[i]] = 0;
distances2[P[i]] = 0;
pq.push(Node{.dist = 0, .index = P[i]});
}
while (!pq.empty()) {
auto [dist, index] = pq.top();
pq.pop();
if (dist > distances2[index])
continue;
if (index == 0)
return dist;
for (auto [x, d] : adj[index]) {
i64 new_dist = dist + d;
if (new_dist < distances[x]) {
distances2[x] = distances[x];
distances[x] = new_dist;
if (distances2[x] != 1e18) {
pq.push(Node{.dist = distances2[x], .index = x});
}
} else if (new_dist < distances2[x]) {
distances2[x] = new_dist;
pq.push(Node{.dist = new_dist, .index = x});
}
}
}
return N;
}
