#include <iostream> #include <vector> #include <set> #include <ctime> using namespace std; #define pb push_back #define ll long long #define fi first #define se second const int N = 1e6 + 5; vector<pair<int,int>> lis[N]; int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]) { ll Dis[n], vi[n] = {}; for (int i = 0; i < n; i++) Dis[i] = 1e18; for (int i = 0; i < m; i++) { int u = R[i][0], v = R[i][1]; lis[u].pb({v, L[i]}); lis[v].pb({u, L[i]}); } set<vector<ll>> pq; for (int i = 0; i < k; i++) { Dis[P[i]] = 0; pq.insert({0, P[i], P[i]}); vi[P[i]] = 1; } while (!pq.empty() && Dis[0] == 1e18) { auto cur = *pq.begin(); pq.erase(pq.begin()); int v = cur[1]; ll d = cur[0]; if (vi[v] != 1) { vi[v]++; continue; } Dis[v] = d; vi[v]++; for (auto &u : lis[v]) { if (vi[u.fi] >= 2 || Dis[u.fi] != 1e18) continue; pq.insert({Dis[v] + u.se, u.fi, v}); } } return Dis[0]; }