Pagini recente » Cod sursa (job #2180351) | Cod sursa (job #1116328) | Cod sursa (job #2569684) | Cod sursa (job #3284516) | Cod sursa (job #1112124)
#include<fstream>
#define M 2000000000
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
struct nod
{
int inf;
int c;
nod * leg;
};
typedef nod* PNod;
PNod L[50001];
int q[800000],cost[50001],n,m,x,y,s,v[15];
void add(int a,int b,int costi)
{
PNod p=new nod;
p->inf=b;
p->c=costi;
p->leg=L[a];
L[a]=p;
}
void bellford(int poz)
{ int i;
q[1]=poz;
for(i=1;i<=n;i++)
cost[i]=M;
cost[poz]=0;
int inc=1,sf=1,ok=0;
while(inc<=sf&&ok==0)
{
for(PNod p=L[q[inc]];p;p=p->leg)
if(cost[p->inf]>cost[q[inc]]+p->c)
{
cost[p->inf]=cost[q[inc]]+p->c;
sf++;
q[sf]=p->inf;
}
inc++;
}
}
int main()
{
int a,b,costi,i,k;
f>>n>>m;
f>>k;
for(i=1;i<=k;i++)
f>>v[i];
for(i=1;i<=m;i++)
{
f>>a>>b>>costi;
add(a,b,costi);add(b,a,costi);
}
if(k==1)
{bellford(1);s+=cost[v[1]];bellford(v[1]);s+=cost[n];g<<s;}
else
{
bellford(1);
for(i=1;i<k;i++)
{
s+=cost[v[i]];
bellford(v[i]);
}
s+=cost[v[n]];
g<<s;
}
return 0;
}