Pagini recente » Cod sursa (job #2544532) | Cod sursa (job #544499) | Cod sursa (job #2579103) | Cod sursa (job #283829) | Cod sursa (job #2547734)
#include <bits/stdc++.h>
#define pii pair<int,int>
#define make_pii(a,b) make_pair(a,b)
#define INF -1
using namespace std;
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");
const int lmt = 2e3+1;
int n,m,k,sum, ndViz;
bool viz[lmt];
vector<int> ctLst;
vector<pii> aList[lmt];
void citire()
{
fin>>n>>m>>k;
ctLst.push_back(1);
for(int i=1;i<=k;++i)
{
int x;
fin>>x;
ctLst.push_back(x);
}
ctLst.push_back(n);
for(int i=1;i<=m;++i)
{
int x,y,z;
fin>>x>>y>>z;
aList[x].push_back(make_pii(y,z));
aList[y].push_back(make_pii(x,z));
}
}
int dijkstra(int src)
{
//rezolva dijkstra
vector<int> dist(n+1,INF);
set<pii> bfsq;
dist[src]=0;
bfsq.insert(make_pii(0,src));
while(!bfsq.empty())
{
pii crnt = *(bfsq.begin());
bfsq.erase(*(bfsq.begin()));
int u = crnt.second;
vector<pii>::iterator i;
for(i=aList[u].begin();i!=aList[u].end();++i)
{
int v = (*i).first;
int weight = (*i).second;
int newDist = dist[u] + weight;
if(dist[v]==INF || dist[v]>newDist)
{
if(dist[v]!=INF)
bfsq.erase(bfsq.find(make_pii(dist[v],v)));
dist[v]=newDist;
bfsq.insert(make_pii(dist[v],v));
}
}
}
//cauta nodul de dist minima nevizitat
//si aduna distanta
int mini = INT_MAX;
int minNod=-1;
vector<int>::iterator i;
for(i=ctLst.begin();i!=ctLst.end();++i)
{
int nod = *i;
if(!viz[nod] && dist[nod]<mini && nod !=n)
{
mini=dist[nod];
minNod=nod;
}
}
if(minNod==-1)
{
minNod=n;
mini = dist[n];
}
sum+=mini;
viz[minNod]=1;
return minNod;
}
int main()
{
citire();
viz[1]=1;
int nod = 1;
while(nod!=n)
{
nod = dijkstra(nod);
}
fout<<sum;
return 0;
}