#include "crocodile.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define ii pair<ll,ll> #define fir first #define sec second const int maxn=1e5; const ll inf=1e18; int n,m; vector<ii>adj[maxn+2]; ll dist[maxn+2][2]; int travel_plan(int N, int M, int r[][2], int l[], int K, int P[]){ n=N,m=M; for(int q=0;q<m;q++){ adj[r[q][0]].push_back({r[q][1],l[q]}); adj[r[q][1]].push_back({r[q][0],l[q]}); } for(int q=0;q<n;q++){ dist[q][0]=dist[q][1]=inf; } priority_queue<ii,vector<ii>,greater<ii> >pq; for(int q=0;q<K;q++){ int x=P[q]; dist[x][0]=dist[x][1]=0; pq.push({0,x}); } while(pq.size()){ auto[jrk,idx]=pq.top();pq.pop(); if(dist[idx][1]!=jrk)continue; for(auto x : adj[idx]){ ll baru=x.sec+jrk; if(dist[x.fir][0]>baru){ dist[x.fir][1]=dist[x.fir][0]; dist[x.fir][0]=baru; if(dist[x.fir][1]!=inf){ pq.push({dist[x.fir][1],x.fir}); } } else if(dist[x.fir][1]>baru){ dist[x.fir][1]=baru; pq.push({dist[x.fir][1],x.fir}); } } } return dist[0][1]; }