Pagini recente » Cod sursa (job #2083343) | Cod sursa (job #2227298) | Cod sursa (job #2419707) | Cod sursa (job #1788529) | Cod sursa (job #1227706)
#include<fstream>
#include<queue>
#define INF 1000000
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
int s, n, m, k, nr, d[1001], v[1001][1001];
bool prieten[1001];
queue <int> c;
void citire()
{
int i, j, x, y, pret;
f>>n>>m>>k;
for(i=1;i<=k;i++)
{
f>>x;
prieten[x]=1;
}
for(i=1;i<=m;i++)
{
f>>x>>y>>pret;
v[x][y]=v[y][x]=pret;
}
}
void bmf(int x)
{
int i, u, p, ok1, poz;
for(i=1;i<=n;i++)d[i]=INF;
d[x]=0;
c.push(x);
while(!c.empty())
{
ok1=0;
p=c.front();
for(i=1;i<=n;i++)
{
if(d[i]>d[p]+v[p][i]&&v[p][i])
{
ok1=1;
d[i]=d[p]+v[p][i];
c.push(i);
}
}
if(!ok1)c.pop();
}
}
int main()
{
int i, j, ultim, mini=INF, poz;
citire();
int nr=k;
bmf(1);
for(i=2;i<=n;i++)
{
if(d[i]<mini&&(prieten[i]||(k==0&&i==n)))
{
mini=d[i];
ultim=i;
}
}
if(nr)nr--;
prieten[ultim]=0;
s+=d[ultim];
while(nr)
{
bmf(ultim);
mini=INF;
for(i=1;i<=n;i++)
{
if(d[i]<mini&&prieten[i]&&i!=ultim)
{
mini=d[i];
poz=i;
}
}
s+=d[poz];
ultim=poz;
nr--;
}
bmf(ultim);
s+=d[n];
g<<s;
f.close();
g.close();
return 0;
}