Cod sursa(job #1721495)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 25 iunie 2016 19:29:25
Problema Team Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include<cstdio>
#include<cstring>
#define MAXN 55
#define MAXV 510
#define INF 1000000000
using namespace std;
int people,vertices,edges;
int cost[MAXN][MAXN],edge[MAXV][MAXV],best[MAXV],destination[MAXN],dp[MAXN][MAXN][MAXN],seen[MAXV];
void Dijkstra(int start){
    int i,j,node;
    for(i=0;i<=vertices;i++)
        best[i]=INF;
    best[start]=0;
    memset(seen,0,sizeof(seen));
    for(i=1;i<=vertices;i++){
        node=0;
        for(j=1;j<=vertices;j++)
            if(seen[j]==0&&best[j]<best[node])
                node=j;
        for(j=1;j<=vertices;j++)
            if(best[node]+edge[node][j]<best[j])
                best[j]=best[node]+edge[node][j];
        seen[node]=1;
    }
}
void Precompute(){
    int i,j;
    for(i=0;i<=people;i++){
        Dijkstra(destination[i]);
        for(j=0;j<=people;j++)
            cost[i][j]=best[destination[j]];;
    }
}
int minimum(int a,int b){
    if(a<b)
        return a;
    return b;
}
int Solve(int i,int j,int start){
    int k;
    if(i>j||(i==j&&i==start))
        return 0;
    if(dp[i][j][start]!=INF)
        return dp[i][j][start];
    for(k=i;k<=j;k++)
        dp[i][j][start]=minimum(dp[i][j][start],Solve(i,k-1,k)+Solve(k+1,j,k)+cost[start][k]);
    return dp[i][j][start];
}
int main(){
    freopen("team.in","r",stdin);
    freopen("team.out","w",stdout);
    int i,j,k,a,b,c;
    scanf("%d%d%d",&people,&vertices,&edges);
    for(i=1;i<=vertices;i++)
        for(j=1;j<=vertices;j++)
            edge[i][j]=INF;
    for(i=1;i<=edges;i++){
        scanf("%d%d%d",&a,&b,&c);
        edge[a][b]=edge[b][a]=c;
    }
    destination[0]=1;
    for(i=1;i<=people;i++)
        scanf("%d",&destination[i]);
    Precompute();
    for(i=0;i<=people;i++)
        for(j=0;j<=people;j++)
            for(k=0;k<=people;k++)
                dp[i][j][k]=INF;
    printf("%d",Solve(1,people,0));
    return 0;
}