Pagini recente » Cod sursa (job #2098848) | Cod sursa (job #421813) | Cod sursa (job #2933125) | Cod sursa (job #1205009) | Cod sursa (job #2149065)
#include <bits/stdc++.h>
#define oo 100005
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
int n,m,k;
int x,y,z,v[20];
int a[2001][2001];
int d[20001],t[20001],p[20001];
void dijkstra(int s)
{ int i,j,k,min;
for(i=1;i<=n;i++)
{ d[i]=a[s][i];
if(i!=s && d[i]!=oo) t[i]=s;
}
p[s]=1;
for(k=1;k<n;k++)
{ min=oo;
for(i=1;i<=n;i++)
if(!p[i] && d[i]<min) { min=d[i]; j=i;
}
for(i=1;i<=n;i++)
if(!p[i])
if(d[i]>d[j]+a[j][i])
{ d[i]=d[j]+a[j][i];
t[i]=j;
}
p[j]=1;
}
}
void drum(int i)
{ if(t[i]) drum(t[i]);
g<<i<<" ";
}
int main()
{
f>>n>>m;
f>>k;
for(int i=1;i<=k;i++)
f>>v[i];
//for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[j]=oo;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=oo;
for(int i=1;i<=m;i++)
{
f>>x>>y>>z;
a[x][y]=a[y][z]=z;
}
//d[1]=0;
dijkstra(1);
/* for(int i=1;i<=n;i++)
{for(int j=1;j<=n;j++)
if(a[i][j]!=oo)
g<<a[i][j]<<" ";
else g<<"0 ";
g<<'\n';
} */
//g<<'\n';g<<'\n';g<<'\n';
/*for(int i=1;i<=n;i++)
if(i!=1)
{g<<1<<"->"<<i<<": ";
drum(i);
g<<"="<<d[i]<<endl;
}*/
if(k==0)
g<<d[n];
else
{
int s=0;
s+=d[v[1]];
for(int i=2;i<=k;i++)
{
dijkstra(v[i]);
s+=d[v[i]];
}
g<<s+d[n];
}
return 0;
}