#include<bits/stdc++.h> #include "crocodile.h" using namespace std; const int MN = 1e5 + 5; using ll = long long; using pii = pair<int,int>; using pli = pair<ll,int>; vector<pii> adj[MN]; ll dist[MN][2]; int wot[MN][2]; int travel_plan (int n, int m, int r[][2], int l[], int k, int e[]) { for (int i = 0; i < m; i++) { adj[++r[i][0]].emplace_back(++r[i][1],l[i]); adj[r[i][1]].emplace_back(r[i][0],l[i]); } memset(dist,0x3f,sizeof dist); priority_queue<pli,vector<pli>,greater<pli>> pq; for (int i = 0; i < k; i++) { ++e[i]; dist[e[i]][0] = dist[e[i]][1] = 0; pq.push({0,e[i]}); } while (!pq.empty()) { ll d = pq.top().first; int cur = pq.top().second; pq.pop(); if (d > dist[cur][1]) continue; for (pii p : adj[cur]) { ll nd = d + p.second, old = dist[p.first][1]; if (nd < dist[p.first][0]) { if (wot[p.first][0] != cur) { dist[p.first][1] = dist[p.first][0]; wot[p.first][1] = wot[p.first][0]; } wot[p.first][0] = cur; dist[p.first][0] = nd; } else if (wot[p.first][0] != cur && nd < dist[p.first][1]) { wot[p.first][1] = cur; dist[p.first][1] = nd; } if (old != dist[p.first][1]) { pq.push({dist[p.first][1],p.first}); } } } return dist[1][1]; }