Pagini recente » Cod sursa (job #530766) | Cod sursa (job #1002805) | Cod sursa (job #1094032) | Cod sursa (job #1630682) | Cod sursa (job #3284833)
#include <bits/stdc++.h>
#include <queue>
#define int long long
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
int n,m,k;
vector<pair<int,int>> v[10001];
priority_queue<int, vector<int>, greater<int>> ubu;
//vector<int> ubu;
int dijkstra(int start, int dest){
vector<int> dist(n+2, INT_MAX);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
dist[start] = 0;
pq.push({0, start});
while(!pq.empty()){
int u = pq.top().second;
pq.pop();
for(auto x : v[u]){
int b = x.first;
int weight = x.second;
if(dist[b] > dist[u] + weight){
dist[b] = dist[u] + weight;
pq.push({dist[b], b});
}
}
}
return dist[dest];
}
signed main()
{
f >> n >> m >> k;
for(int i = 1; i<=k; i++){
int x;
f >> x;
ubu.push(x);
}
for(int i = 1; i<=m; i++){
int a,b,c;
f >> a >> b >> c;
v[a].push_back({b, c});
v[b].push_back({a, c});
}
int l = 0, start = 1;
while(!ubu.empty()){
int x = ubu.top();
ubu.pop();
l += dijkstra(start, x);
start = x;
}
// for(int x : ubu){
// l += dijkstra(start, x);
// start = x;
// }
l+= dijkstra(start, n);
g << l;
}