#include"crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<long long,long long>
#define fi first
#define se second
const int MAXN=1e5+5;
const long long INF=1e18;
long long dp[MAXN][2];
vector<ii> ds[MAXN];
int travel_plan(int n,int m,int R[][2],int L[],int k,int P[])
{
priority_queue< ii,vector<ii>,greater<ii> > pq;
for(int i=0;i<n;i++) dp[i][0]=dp[i][1]=INF,ds[i].clear();
for(int i=0;i<m;i++) ds[R[i][0]].push_back({R[i][1],L[i]}),ds[R[i][1]].push_back({R[i][0],L[i]});
for(int i=0;i<k;i++) dp[P[i]][0]=dp[P[i]][1]=0,pq.push({0,P[i]});
while(!pq.empty())
{
long long a=pq.top().fi,b=pq.top().se;
pq.pop();
if(dp[b][1]==INF||dp[b][1]<a) continue;
for(auto v:ds[b]) if(dp[v.fi][0]>a+v.se)
{
if(dp[v.fi][0]<dp[v.fi][1]) pq.push({dp[v.fi][0],v.fi});
dp[v.fi][1]=dp[v.fi][0],dp[v.fi][0]=a+v.se;
}
else if(dp[v.fi][1]>a+v.se)
{
dp[v.fi][1]=a+v.se;
pq.push({dp[v.fi][1],v.fi});
}
}
return dp[0][1];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |