Cod sursa(job #1022361)

Utilizator monica11Szekely Monica monica11 Data 5 noiembrie 2013 11:45:03
Problema Ubuntzei Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<fstream>
#include<cstring>
#include<algorithm>
#define pb push_back
#define inf 99999999999
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
int n, m, k;
int b[2005];
long long a[2005][2005];
int viz[2005],c[2005];
long long s=1000000000,sint=0;
void init()
{
    int i,j;
    for(i=1;i<=n;++i)
       for(j=1;j<=n;++j)
            a[i][j]=1000000000;
}
void citire()
{
    int i,x,y,z;
    f>>n>>m;
    f>>k;
    for(i=1;i<=k;++i)
       f>>b[i];
    init();
    for(i=1;i<=m;++i)
    {
        f>>x>>y>>z;
        a[x][y]=z;
        a[y][x]=z;
    }
    b[0]=1;
    b[k+1]=n;
    c[0]=0;
    c[k+1]=k+1;
    viz[0]=1;
    viz[k+1]=1;
}
void rezolva()
{
    int i,j,k;
  for(k=1;k<=n;++k)
    for(i=1;i<=n;++i)
       for(j=1;j<=n;++j)
            if(i!=k&&j!=k&&i!=j&&(a[i][j]>a[i][k]+a[k][j]||a[i][j]==0))
                a[i][j]=a[i][k]+a[k][j];
   if(k==0)
   s=a[1][n];
}
void back(int x)
{
    int i;
    if(x==k+1)
    {
        if(s>sint+a[b[c[x-1]]][b[c[x]]])
          s=sint+a[b[c[x-1]]][b[c[x]]];
    }
    else
    {
        for(i=1;i<=k;++i)
           if(viz[i]==0)
           {
               viz[i]=1;
               c[x]=i;
               sint=sint+a[b[c[x-1]]][b[c[x]]];
               back(x+1);
               viz[i]=0;
               sint=sint-a[b[c[x-1]]][b[c[x]]];
           }
    }
}
int main()
{
    citire();
    rezolva();
    back(1);
    g<<s;
    return 0;
}