Pagini recente » Cod sursa (job #652708) | Cod sursa (job #2937309) | Cod sursa (job #2539483) | Cod sursa (job #2442573) | Cod sursa (job #891972)
Cod sursa(job #891972)
//#include<iostream>
#include<fstream>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;
#define edge pair<int,int>
#define mp make_pair
#define pb push_back
#define node second
#define cost first
const int MAX_SIZE=2e3+3;
const int oo=(1<<30)-1;
vector<edge> graph[MAX_SIZE];
vector<int> dist(MAX_SIZE,oo);
vector<edge>::iterator it,end;
priority_queue<edge, vector<edge>, greater<edge> > heap;
int main ()
{
ifstream in("ubuntzei.in");
ofstream out("ubuntzei.out");
int n,m,k,c[MAX_SIZE],viz[MAX_SIZE],drum=0;
in>>n>>m>>k;
c[0]=1;
c[k+1]=n;
for(int i=1;i<=k;i++)
in>>c[i];
sort(c,c+k+1);
for(int i=1;i<=m;i++)
{
int cTo,cFrom,cCost;
in>>cFrom>>cTo>>cCost;
graph[cFrom].pb(mp(cCost,cTo));
graph[cTo].pb(mp(cCost,cFrom));
}
for(int i=0;i<=k+1;i++)
viz[i]=0;
for(int i=0;i<=k;i++)
{
if(c[i]==c[i+1])
continue;
heap.push(mp(0,c[i]));
dist[c[i]]=0;
while(!heap.empty())
{
int current=heap.top().node;
heap.pop();
it=graph[current].begin();
end=graph[current].end();
for(;it!=end;++it)
if(dist[current]+it->cost<dist[it->node])
{
dist[it->node]=dist[current]+it->cost;
heap.push(mp(dist[it->node],it->node));
}
}
int min=i+1;
viz[min]=1;
for(int j=1;j<=k;j++)
{
if(!viz[j])
if(dist[c[j]]<dist[c[min]])
min=j;
}
i=min-1;
drum+=dist[c[min]];
dist.clear();
//dist.assign(MAX_SIZE,oo);
}
//viz[k+1]=1;
out<<drum;
in.close();
out.close();
return 0;
}