Pagini recente » Cod sursa (job #1574597) | Cod sursa (job #571131) | Cod sursa (job #2670830) | Cod sursa (job #1346140) | Cod sursa (job #2841351)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
const int inf = 10000000;
using namespace std;
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");
struct muchie{
int nod,cost;
};
vector<muchie>v[2500];
int n,m,k,x,y,cost,NOD[1000],sum;
bool ap[1000];
int D[20][2010];
void dijk(int x,int d[])
{
queue<int>q;
for(int i=1;i<=n;i++)
d[i]=inf;
d[x]=0;
q.push(x);
while(!q.empty())
{
int nod = q.front();
q.pop();
for(auto it:v[nod])
if(d[it.nod] > d[nod] + it.cost)
{
d[it.nod] = d[nod] + it.cost;
q.push(it.nod);
}
}
}
int main() {
fin>>n>>m>>k;
for(int i=1;i<=k;i++)
fin>>NOD[i];
for(int i=1;i<=m;i++)
{
fin>>x>>y>>cost;
v[x].push_back({y,cost});
v[y].push_back({x,cost});
}
dijk(1, D[0]);
for(int i=1;i<=k;i++)
dijk(NOD[i], D[i]);
int vizitate = 0,ant=0;
while(vizitate < k)
{
int pmin=0,vmin=inf;
for(int i=1;i<=k;i++)
if(!ap[i] && D[ant][NOD[i]] < vmin)
{
vmin = D[ant][NOD[i]];
pmin = i;
}
sum += vmin;
ap[pmin]=1;
vizitate++;
ant = pmin;
}
sum += D[ant][n];
fout<<sum;
return 0;
}