记录编号	126370	评测结果	AAAAAAAAAA
题目名称	[東方S2] 伊吹萃香	最终得分	100
用户昵称	奇诺	是否通过	通过
代码语言	C++	运行时间	0.090 s
提交时间	2014-10-12 09:54:58	内存使用	37.50 MiB

#include<cstdio>
//-----------------------------------------------------------------------
inline void Max(int &a,int b) { if (a<b) a=b;    }
inline void Min(int &a,int b) { if (a>b) a=b;    }
inline int  Abs(int  a      ) { return a>0?a:-a; }
//-----------------------------------------------------------------------
int  n,m;
int  i,j;

int  tmp;

int  fla=1;

int  c[5002],h[5002];

int  l[100000],w[100000],t[100000],cost[100000],T=0;

int  sta[2333333],tim[2333333];
int  che[2][2333333],now,top,tai=1;

int  dis[2][5002];
//-----------------------------------------------------------------------
inline void add(int a,int b) 
{ 
	l[++T]=w[a]; 
	w[a]=T;
	t[T]=b; 
	scanf("%d",&cost[T]); 
}
//-----------------------------------------------------------------------
int  main ( )
{
	freopen ( "suika.in"  , "r" , stdin  );
	freopen ( "suika.out" , "w" , stdout );
	scanf("%d%d",&n,&m);
	for (i=1; i<=n; i++) scanf("%d",&c[i]);
	for (i=1; i<=n; i++) scanf("%d",&h[i]);
	for (i=1; i<=n; i++) add(i,i);
	while (m--)
	{
		scanf("%d%d",&i,&j);
		add(i,j);
	}
	//--
	for (i=1; i<=n; i++) dis[0][i]=dis[1][i]=233333333;
	dis[0][1]=0;
	che[0][1]=1;
	sta[1]=1;
	tim[1]=0;
	//--
	for (top=1; top<=tai; top++)
	{
		now=sta[top];
		for (i=w[now]; i; i=l[i])
		{
			tmp=cost[i];
			if (c[t[i]]^c[now])
			if (c[now]) tmp+=(1-2*tim[top])*Abs(h[now]-h[t[i]]);
				   else tmp-=(1-2*tim[top])*Abs(h[now]-h[t[i]]);
			Max(tmp,0);
			if (t[i]==now&&!(c[now]^tim[top])) tmp=0;
			//--
			if (dis[tim[top]][now]+tmp<dis[1-tim[top]][t[i]])
			{
				dis[1-tim[top]][t[i]]=dis[tim[top]][now]+tmp;
				if (!che[1-tim[top]][t[i]])
				{
					che[1-tim[top]][t[i]]=1;
					sta[++tai]=t[i];
					tim[  tai]=1-tim[top];
				}
			}
		}
		che[tim[top]][now]=0;
	}
	Min(dis[0][n],dis[1][n]);
	printf("%d",dis[0][n]);
}