#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int inf=1e9+7;
int dist[maxn][2], n;
vector<pair<int,int>>v[maxn];
void dijkstra(vector<int> ini){
for(int i=1;i<=n;i++) dist[i][0]=dist[i][1]=inf;
for(int a : ini) dist[a][0]=dist[a][1]=0;
set<pair<int,int>> s;
for(int i=1;i<=n;i++) s.insert({dist[i][1],i});
while(!s.empty()){
auto f=s.begin();
int u=f->second;
s.erase(f);
for(pair<int,int> p : v[u]){
int viz=p.first, w=p.second;
if(dist[u][1]+w<dist[viz][0]){
s.erase({dist[viz][1],viz});
dist[viz][1]=dist[viz][0];
dist[viz][0]=dist[u][1]+w;
s.insert({dist[viz][1],viz});
}else if(dist[u][1]+w<dist[viz][1]){
s.erase({dist[viz][1],viz});
dist[viz][1]=dist[u][1]+w;
s.insert({dist[viz][1],viz});
}
}
}
}
int travel_plan(int N, int m, int R[][2], int L[], int k, int P[]){
n=N;
for(int i=0;i<m;i++){
v[R[i][0]+1].push_back({R[i][1]+1,L[i]});
v[R[i][1]+1].push_back({R[i][0]+1,L[i]});
}
vector<int> aux;
for(int i=0;i<k;i++) aux.push_back(P[i]);
dijkstra(aux);
return dist[1][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... |