#include<bits/stdc++.h>
using namespace std;
//#define name "InvMOD"
#ifndef name
#include "crocodile.h"
#endif // name
#define sz(v) (int)(v).size()
int travel_plan(int n, int m, int R[][2], int L[], int K, int P[]){
vector<vector<pair<int,int>>> adj(n, vector<pair<int,int>>());
for(int i = 0; i < m; i++){
int u = R[i][0], v = R[i][1];
adj[u].emplace_back(v, L[i]);
adj[v].emplace_back(u, L[i]);
}
const int inf = 1e9;
vector<vector<int>> dist(n, vector<int>(2, inf));
for(int i = 0; i < K; i++){
int x = P[i];
dist[x][0] = 0;
dist[x][1] = 0;
}
priority_queue<pair<int, int>> pq;
for(int i = 0; i < K; i++) pq.push({0, P[i]});
while(!pq.empty()){
pair<int,int> eq = pq.top(); pq.pop();
int cur_dist = -eq.first, x = eq.second;
if(cur_dist == inf || cur_dist > dist[x][1]) continue;
for(pair<int,int> e : adj[x]){
int v = e.first, w = e.second;
if(cur_dist + w < dist[v][0]){
if(dist[v][0] < dist[v][1])
pq.push({-dist[v][0], v});
dist[v][1] = dist[v][0];
dist[v][0] = cur_dist + w;
}
else if(cur_dist + w < dist[v][1]){
dist[v][1] = cur_dist + w;
pq.push({-dist[v][1], v});
}
}
}
return dist[0][1];
}
#ifdef name
int32_t main(){
freopen(name".INP", "r", stdin);
freopen(name".OUT", "w", stdout);
int n,m,k; cin >> n >> m >> k;
int E[m][2], L[m], P[k];
for(int i = 0; i < m; i++){
cin >> E[i][0] >> E[i][1] >> L[i];
}
for(int i = 0; i < k; i++){
cin >> P[i];
}
cout << travel_plan(n, m, E, L, k, P) << "\n";
return 0;
}
#endif // name
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |