Pagini recente » Cod sursa (job #2609238) | Cod sursa (job #2221500) | Cod sursa (job #2692086) | Cod sursa (job #2704689) | Cod sursa (job #2494622)
#include <bits/stdc++.h>
#define MOD 1999999973
#define ull unsigned long long
#define inf 2000001
using namespace std;
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");
vector<pair<int,int>> G[50005];
priority_queue<pair<int,int>> Q;
int val[5005];
int viz[5005];
int eloc[5005];
int loc[100];
int n,m,k,sumsol;
int findmin(){
int sol;
while(viz[Q.top().second] == 1){
Q.pop();
}
sol = Q.top().second;
Q.pop();
return sol;
}
void Dijkstra(int a){
int i,j,vecin,cost,minim;
while(!Q.empty()){
Q.pop();
}
for(i = 1; i <= n; ++i){
viz[i] = 0;
}
for(i = 1; i <= n; ++i){
if(i != a){
val[i] = inf;
}else{
val[i] = 0;
}
Q.push(make_pair(-val[i],i));
}
for(i = 1; i <= n; ++i){
minim = findmin();
viz[minim] = 1;
for(j = 0; j < G[minim].size(); j++){
vecin = G[minim][j].first;
cost = G[minim][j].second;
if(val[vecin] > val[minim] + cost){
val[vecin] = val[minim] + cost;
Q.push(make_pair(-val[vecin],vecin));
}
}
}
}
int main()
{
int i,j,a1,a2,c1,nrloc,urm,minim;
fin>>n>>m>>k;
nrloc = k;
for(i = 1; i <= k; ++i){
fin>>loc[i];
eloc[loc[i]] = 1;
}
for(i = 1; i <= m; ++i){
fin>>a1>>a2>>c1;
G[a1].push_back(make_pair(a2,c1));
G[a2].push_back(make_pair(a1,c1));
}
Dijkstra(1);
while(nrloc--){
minim = inf;
for(i = 1; i <= n; i++){
if(eloc[i]){
if(minim > val[i]){
minim = val[i];
urm = i;
}
}
}
eloc[urm] = 0;
sumsol += minim;
Dijkstra(urm);
}
sumsol += val[n];
fout<<sumsol<<endl;
return 0;
}