Cod sursa(job #295724)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 3 aprilie 2009 17:12:28
Problema Team Scor 40
Compilator cpp Status done
Runda Simulare Marime 3.04 kb
#include <stdio.h>
#include <vector>
#include <string.h>

#define pb push_back
#define maxn 550
#define maxp 55

using namespace std;

long len, n, i, j, k, m, p, c[maxn][maxn], dest[maxn], a, b, cost, coa[maxn*maxn], nod, fiu;
vector <long> v[maxn], w[maxn];
long d[maxp][maxp][maxp];

long min(long a, long b)
{
    if(a<b) return a;
    return b;
}

int main()
{
    freopen("team.in", "r", stdin);
    freopen("team.out", "w", stdout);
    scanf("%d%d%d", &p, &n, &m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d %d", &a, &b, &cost);
        v[a].pb(b);
        v[b].pb(a);
        w[a].pb(cost);
        w[b].pb(cost);
    }
    long inf = 50000000;
  /*  memset(c, inf, sizeof(c));
    memset(d, inf, sizeof(d));*/
    for(i=0; i<=n; i++)
    {
        for(j=0; j<=n; j++)
        {
            c[i][j]=inf;
        }
    }
    for(i=0; i<=p+1; i++)
    {
        for(j=0; j<=p+1; j++)
        {
            for(k=0; k<=p+1; k++)
            {
                d[i][j][k]=inf;
            }
        }
    }
    for(i=1; i<=p; i++)
    {
        scanf("%d", &dest[i]);
    }
    dest[p+1]=1;
    for(i=1; i<=p+1; i++)
    {
        coa[0]=1;
        len=dest[i];
        coa[1]=len;
        c[len][len]=0;
        for(j=1; j<=coa[0]; j++)
        {
            nod=coa[j];
            for(k=0; k<v[nod].size(); k++)
            {
                fiu=v[nod][k];
                if(c[len][fiu]>w[nod][k]+c[len][nod])
                {
                    c[len][fiu]=w[nod][k]+c[len][nod];
                    coa[0]++;
                    coa[coa[0]]=fiu;
                }
            }
        }
    }
 /*   for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            printf("%d ", c[i][j]);
        }
        printf("\n");
    }*/
    dest[p+1]=1;
    for(len=0; len<p; len++)
    {
        if(len)
        {
            for(i=1; i+len<=p; i++)
            {
                d[i][i+len][i]=d[i+1][i+len][i];
                d[i][i+len][i+len]=d[i][i+len-1][i+len];
                for(j=1; j<len; j++)
                {
                    d[i][i+len][i+j]=d[i][i+j-1][i+j]+d[i+j+1][i+len][i+j];
                }
            }
        }
        else
        {
            for(i=1; i<=p; i++)
            {
                d[i][i][i]=0;
            }
        }
        for(i=1; i+len<=p; i++)
        {
          //  printf("%d %d: ", i, i+len);
           // for(k=1; k<=p+1; k++)
            {
                for(j=0; j<=len; j++)
                {
                    if(i>1) d[i][i+len][i-1]=min(d[i][i+len][i-1], d[i][i+len][i+j]+c[dest[i-1]][dest[i+j]]);
                    if(i+len<=p) d[i][i+len][i+len+1]=min(d[i][i+len][i+len+1], d[i][i+len][i+j]+c[dest[i+len+1]][dest[i+j]]);
                }
         //       printf("%d ", d[i][i+len][k]);
            }
        //    printf("\n");
        }
      //  printf("*\n");
    }
    printf("%d\n", d[1][p][p+1]);
    return 0;
}