#include "crocodile.h" #include <bits/stdc++.h> using namespace std; using ll = long long; //#define int ll //using P = pair<int, int>; #define all(x) x.begin(), x.end() #define rep(i, l, n) for (int i = l; i < (n); ++i) #define sz(x) (int)x.size() const char nl = '\n'; const int mod = 1e9+7; const int NMAX = 1010; const int inf = 1e9+10; vector<pair<int, int>> g[NMAX]; bool specific[NMAX]; int mn1[NMAX], mn2[NMAX]; int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { memset(specific, false, sizeof specific); rep(i, 0, M) g[R[i][0]].push_back({R[i][1], L[i]}), g[R[i][1]].push_back({R[i][0], L[i]}); rep(i, 0, K)specific[P[i]] = 1; rep(i, 0, N)mn1[i] = mn2[i] = inf; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; rep(i, 0, K) { mn1[P[i]] = 0; pq.push({0, P[i]}); } while (!pq.empty()) { auto [dis, node] = pq.top(); pq.pop(); //cout << node << " " << dis << nl; if (mn2[node] != inf)continue; if (dis < mn1[node]) { assert(mn1[node] == inf); mn1[node] = dis; } else { mn2[node] = dis; //cout << "im here" << nl; for (auto [son, weight]: g[node]) pq.push({dis+weight, son}); } } return mn2[0]; }