Cod sursa(job #115272)

Utilizator ScrazyRobert Szasz Scrazy Data 16 decembrie 2007 11:55:09
Problema Gather Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasele 11-12 Marime 1.37 kb
#include <stdio.h>
#define NMAX 760
#define inf 32000

int n, m, k;
int a, b, c, d;
int C[NMAX][NMAX];
int M[NMAX][NMAX]; 
int nod[NMAX];
int D[NMAX], pre[NMAX], Q[NMAX];
long sol;

void djikstra(int x,int y)
{
    int i, j;
    int dmin=inf, vfmin;
    for (i=1; i<=n; ++i) Q[i]=D[i]=pre[i]=0;
    for (i=1; i<=n; ++i)
    {
	D[i]=C[x][i]; pre[i]=x;
    }
    Q[x]=1;pre[x]=0;

    for (j=1; j<n; ++j)
    {
	dmin=inf;
	for (i=1; i<=n; ++i)
	    if (!Q[i] && dmin>D[i])
	    {
		dmin=D[i];
		vfmin=i;
	    }
	Q[vfmin]=1;
	for (i=1; i<=n; ++i)
	    if (!Q[i] && D[i]>dmin+C[vfmin][i])
	    {
		pre[i]=vfmin;
		D[i]=dmin+C[vfmin][i];
	    }
    }
}



int main()
{
    freopen("gather.in","r",stdin);
    freopen("gather.out","w",stdout);

    int i, j, l, loc, min, mini;
    scanf("%d %d %d", &k, &n, &m);

    for (i=1; i<=k; ++i)
    {
	scanf("%d", &a);
	nod[a]=1;
    }
    for (i=1; i<=n; ++i)
	for (j=1; j<=n; ++j)
	    C[i][j]=inf;

    for (i=1; i<=m; ++i)
    {
	scanf("%d %d %d %d", &a, &b, &c, &d);
	C[a][b]=C[b][a]=c;
	M[a][b]=M[b][a]=d;
    } 

    loc=1;
    for (i=1; i<=k; ++i)
    {
	djikstra(loc,i);
	min=inf;
	mini=1;
	for (j=1; j<=n; ++j)
	    if (min>D[j] && nod[j]) {min=D[j];mini=j;}
	sol+=min*i;
	loc=mini;
	for (j=1; j<=n; ++j)
	    for (l=1; l<=n; ++l)
		if (M[j][l]==i) C[j][l]=inf;
    }

    printf("%ld", sol);

    fclose(stdin);
    fclose(stdout);
    return 0;
}