#include <bits/stdc++.h> #include "crocodile.h" using namespace std; const int mxN = 200005; const int inf = 2e9 + 7; vector<pair<int, int>> adj[mxN]; int dp[mxN][2]; int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { for(int i = 0; i < N; ++i){ adj[i].clear(); dp[i][0] = dp[i][1] = inf; } 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]}); } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for(int i = 0; i < K; ++i){ pq.push({0, P[i]}); dp[P[i]][0] = dp[P[i]][1] = 0; }; while(pq.size()){ auto [dist, u] = pq.top(); pq.pop(); if(dist > dp[u][1]) continue; for(auto [v, w] : adj[u]){ int k = dist + w; if(dp[v][0] > k){ if(dp[v][0] < dp[v][1]) pq.push({dp[v][0], v}); swap(dp[v][0], dp[v][1]); dp[v][0] = k; }else if(dp[v][1] > k){ dp[v][1] = k; pq.push({dp[v][1], v}); } } } return dp[0][1]; }