Pagini recente » Cod sursa (job #1433500) | Cod sursa (job #1297001) | Cod sursa (job #808616) | Cod sursa (job #2160221) | Cod sursa (job #890678)
Cod sursa(job #890678)
#include<fstream>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>
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");
unsigned long long n,m,k,c[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;i++)
{
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));
}
}
drum+=dist[c[i+1]];
dist.clear();
}
out<<drum;
in.close();
out.close();
return 0;
}