d_tle.cpp

ACM World Final 2008题目程序代码

// not accepted yet (need your help! )
#include <cstdio>
#include <cstring>
using namespace std;

int ncp,nroad,ncm,t,helen,holen,ro[200],lenno[200];
bool cp[110];

struct etype
{
	int ds,dt,t,len,no,cfm;
	bool v;
	etype *next,*pair;
	etype(){}
	etype(int ds_,int dt_,int t_,int len_,int no_,etype* next_):
		ds(ds_),dt(dt_),t(t_),len(len_),
		no(no_),cfm(0),next(next_),v(false){}
} *e[110],*m;

struct state
{
	int no,d,dlt,rosize;
} now,fb;

void calcmr()
{
	int dmax=0;
	m=0;
	for(etype *i=e[now.no];i;i=i->next)
	{
		if(cp[now.no] && i->v)continue;
		int d=(i->ds+360-now.d)%360;
		bool r=d>180;
		if(r)d=360-d;
		d+=d+r;
		if(d>dmax)dmax=d,m=i;
	}
}

void fallback(int x)
{
	holen+=x;
	now=fb;
	fb.no=0;
}

void go()
{
	calcmr();
	if(!m)return fallback(fb.dlt-now.dlt);
	if(cp[now.no])
		if(fb.no)return fallback(fb.dlt-now.dlt);
		else
		{
			fb.rosize=now.rosize;
			fb.no=now.no;
			fb.d=m->ds;
			now.dlt=fb.dlt;
		}
	m->v=true;
	if(fb.no)
		if(m->cfm)
			if(now.dlt<m->cfm)return fallback(fb.dlt+now.dlt);
			else fb.no=0;
		else
			if(now.dlt<m->len)return fallback(fb.dlt+now.dlt);
			else now.dlt-=m->len;
	m->pair->v=true;
	ro[++now.rosize]=m->no;
	holen+=m->len;
	now.no=m->t;
	now.d=m->dt;
}

int main()
{
	for(int te=1;scanf("%d %d %d",&ncp,&nroad,&ncm),nroad;++te)
	{
		scanf("%d %d %d %d",&fb.dlt,&now.no,&t,&now.d);
		now.d=(now.d+180)%360;
		memset(cp,0,sizeof(cp));
		while(ncp--)
		{
			int t;
			scanf("%d",&t);
			cp[t]=true;
		}
		memset(e,0,sizeof(e));
		for(int i=1;i<=nroad;++i)
		{
			int n1,d1,n2,d2,len;
			scanf("%d %d %d %d %d",&n1,&n2,&d1,&d2,&len);
			e[n1]=new etype(d1,d2,n2,len,i,e[n1]);
			e[n2]=new etype(d2,d1,n1,len,i,e[n2]);
			e[n1]->pair=e[n2];
			e[n2]->pair=e[n1];
			lenno[i]=len;
		}
		while(ncm--)
		{
			int vno,eno,dis;
			scanf("%d %d %d",&vno,&eno,&dis);
			for(etype *i=e[vno];i;i=i->next)if(i->no==eno)
			{
				i->cfm=dis;
				i->pair->cfm=i->len-dis;
			}
		}
		helen=holen=now.rosize=fb.no=0;
		while(fb.no || now.no!=t)go();
		for(int i=1;i<=now.rosize;++i)helen+=lenno[ro[i]];
		printf("Case %d:\n",te);
		printf("   Length of hare's route is %d\n",helen);
		printf("   Length of hound's search is %d\n",holen);
		printf("   Route:");
		for(int i=1;i<=now.rosize;++i)printf(" %d",ro[i]);
		printf("\n\n");
	}
	return 0;
}