Pagini recente » Cod sursa (job #1065136) | Cod sursa (job #1287633) | Cod sursa (job #2575968) | Cod sursa (job #3255061) | Cod sursa (job #697621)
Cod sursa(job #697621)
#include<cstdio>
#define dim 2001
#define inf 0x3f3f3f3f
#include<algorithm>
using namespace std;
long dist[dim][dim],d,distmin=inf;
int n,m,kk,p[16],sol[16],uz[16];
inline void citire()
{
freopen("ubuntzei.in","r",stdin);
scanf("%d%d",&n,&m);
scanf("%d",&kk);
for(int i=1;i<=kk;++i)
scanf("%d",&p[i]);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i!=j)
dist[i][j]=inf;
for(;m;--m)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
dist[x][y]=c;
dist[y][x]=c;
}
}
inline void roy_floyd()
{
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
inline void back(int k)
{
if(k==kk+1)
{
d=0;
d=dist[1][ p [ sol[1] ] ];
for(int i=1;i<n;++i)
d+=dist[ p[sol[i] ] ][ p[sol[i+1] ] ];
d+= dist[ p[sol[kk] ] ][n];
distmin=min(d,distmin);
}
else
{
for(int i=1;i<=kk;++i)
if(!uz[i])
{
uz[i]=1;
sol[k]=i;
back(k+1);
uz[i]=0;
}
}
}
inline void afisare()
{
freopen("ubuntzei.out","w",stdout);
printf("%d\n",distmin);
}
int main()
{
citire();
roy_floyd();
back(1);
afisare();
}