Cod sursa(job #29238)

Utilizator lluckyLuca Vlad llucky Data 8 martie 2007 20:10:58
Problema Magazin Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<stdio.h>
#include<stdlib.h>
#define MAXS 50001

int p,n,m,d,prod[MAXS][2],viz[MAXS],dist,v;

inline int MIN(int a, int b)
{
 if(a < b)
	return a;
 return b;
}

int close(int &x, int &y)
{
 int dr,i,xm,ym,dm=n*m,im;
 if(v==p) return 0;
 for(i=1;i<=p;i++)
	 if(!viz[i])
		{
		 if(prod[i][0]==x) dr=abs(prod[i][1]-y);
		 else dr=abs(prod[i][0]-x)*d+MIN(y+prod[i][1]-1,2*(m+1)-(y+prod[i][1]));
		 if(dr<dm) {dm=dr; xm=prod[i][0]; ym=prod[i][1]; im=i;}
		}
 x=xm;
 y=ym;
 viz[im]=1;
 v++;
 return dm;
}

int main(void)
{
int i,j,xb,yb,xe,ye;
FILE *f;
f=fopen("magazin.in","r");
fscanf(f,"%d %d %d %d",&p,&n,&m,&d);
for(i=1;i<=p;i++)
 fscanf(f,"%d %d",&prod[i][0],&prod[i][1]);
fclose(f);
xb=yb=1;
xe=n; ye=1;
while(v!=p)
 dist=dist+close(xb,yb)+close(xe,ye);
if(xe==xb) dist+=abs(yb-ye);
		 else dist+=abs(xb-xe)*d+MIN(ye+yb-1,2*(m+1)-(ye+yb));
f=fopen("magazin.out","w");
fprintf(f,"%d\n",dist);
fclose(f);
return 0;
}