#include<bits/stdc++.h> #include "crocodile.h" typedef long long ll; using namespace std; typedef pair<ll, ll> pll; const ll inf = 1e9; #define f first #define s second int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) { vector<vector<pll>> adj(n); for (ll 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<pll, vector<pll>, greater<>> pq; vector<pll> dist(n, {inf, inf}); auto test = [&](ll val, ll b) -> bool { bool yes = 0; if (val < dist[b].f) { dist[b].s = dist[b].f; dist[b].f = val; yes = 1; } else if (val < dist[b].s) { dist[b].s = val; yes = 1; } return yes; }; for (ll i = 0; i < k; i++) pq.push({0, p[i]}), dist[p[i]].f = dist[p[i]].s = 0; while (pq.size()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u].s) continue; for (auto& [v, wt] : adj[u]) { if (d + wt < dist[v].f) { if (dist[v].f < dist[v].s) pq.push({dist[v].f, v}); dist[v].s = dist[v].f; dist[v].f = d + wt; } else if (d + wt < dist[v].s) { dist[v].s = d + wt; pq.push({dist[v].s, v}); } // if (test(dist[u].s + wt, v) && dist[v].s != inf) pq.push({dist[v].s, v}); } } return dist[0].s; }