Pagini recente » Cod sursa (job #87319) | Cod sursa (job #630417) | Cod sursa (job #1264615) | Cod sursa (job #389751) | Cod sursa (job #698398)
Cod sursa(job #698398)
#include<fstream>
#include<iostream>
using namespace std;
int v[100],s[100],mini=1000,n;
void csere (int p[100], int i, int j)
{
int s;
s=p[i];
p[i]=p[j];
p[j]=s;
}
void rekurzio (int p[100],int x,int k,int t[500][500])
{
int i,q=0;
if (k==x+1)
{
q=q+t[1][v[1]];
for (i=1;i<x;i++)
{
q=q+t[v[i]][v[i+1]];
}
q=q+t[v[i]][n];
if(q<mini) mini=q;
}
else
{
for (i=1;i<=x;i++)
{
if (s[i]==0) {v[k]=p[i];s[i]=1;rekurzio(p,x,k+1,t); s[i]=0;v[k]=0;}
}
}
}
int main()
{
int t[500][500]={0},i,j,k,m,a,b,x,c,p[100],s=0;
for(i=0;i<500;i++)
for(j=0;j<500;j++)
if(i!=j) t[i][j]=1000;
fstream f,g;
f.open("ubuntzei.in",ios::in);
f>>n>>m>>x;
for(i=1;i<=x;i++)
f>>p[i];
for(i=1;i<=m;i++)
{
f>>a;
f>>b;
f>>c;
t[a][b]=c;
t[b][a]=c;
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if((t[i][j]>t[i][k]+t[k][j])&&(t[i][k]!=0)&&(t[k][j]!=0))
t[i][j]=t[i][k]+t[k][j];
if(x>0)
{
rekurzio(p,x,1,t);
}
else mini=t[1][n];
g.open("ubuntzei.out",ios::out);
g<<mini;
}