Pagini recente » Cod sursa (job #3157470) | Cod sursa (job #1151706) | Cod sursa (job #931621) | Cod sursa (job #2544692) | Cod sursa (job #2145283)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>
#define nm 10005
#define inf (1<<30)
using namespace std;
ifstream in("ubuntzei.in");
ofstream out("ubuntzei.out");
vector < pair < int , int > > graf[nm];
int s[nm],d[nm],i,n,m,k,oras[nm],x,y,c,distanta;
bitset <nm> vizitat;
struct comp{
bool operator()(int x, int y){
return d[x]>d[y];
}
};
priority_queue <int, vector < int > , comp > q;
void dij(int sursa){
for(i=1;i<=n;++i){
d[i]=inf;
}
d[sursa]=0;
vizitat[sursa]=true;
q.push(sursa);
vector < pair < int , int > > ::iterator it;
while(!q.empty()){
int nodcurent=q.top();
q.pop();
vizitat[nodcurent]=false;
for(it=graf[nodcurent].begin();it!=graf[nodcurent].end();++it){
int vecin=it->first;
int cost =it->second;
if(d[vecin]>d[nodcurent]+cost){
d[vecin]=d[nodcurent]+cost;
if(!vizitat[vecin]){
vizitat[vecin]=true;
q.push(vecin);
}
}
}
}
}
void afiseaza ()
{
int i;
for (i=1;i<=n;i++)
if (d[i]!=inf)
out<<d[i]<<" ";
else out<<"0 ";
out<<"\n";
}
int main()
{
in>>n>>m>>k;
for(int i=1;i<=k;++i) in>>oras[i];
sort(oras+1,oras+k+1);
for(int i=1;i<=m;++i){
in>>x>>y>>c;
graf[x].push_back(make_pair(y,c));
graf[y].push_back(make_pair(x,c));
}
if(k==0){
dij(1);
out<<d[n];
return 0;
}
distanta=0;
dij(oras[1]);
distanta+=d[1];
for(int omom=2;omom<=k;++omom){
dij(oras[omom]);
distanta+=d[oras[omom-1]];
}
distanta+=d[n];
out<<distanta<<' ';
return 0;
}