记录编号	41680	评测结果	AAWWWWWWWW
题目名称	[東方S2] 伊吹萃香	最终得分	20
用户昵称	Truth.Cirno	是否通过	未通过
代码语言	C++	运行时间	0.291 s
提交时间	2012-08-08 21:56:01	内存使用	95.78 MiB

#include <cstdio>
using namespace std;

const int MAXNUM=1000000000;

short w[5001],s[5001],waynum[5001],way[5001][5001],dis[5001][5001];
int f[2][5001]/*,que[10010]={0,1},cost[10010]*/;
bool hei[2][5001],used[2][5001]/*,tim[5001],used[5001]={0,1},stay[5001]*/;

int mtoz(int x)
{
	if (x>0)
		return(x);
	return(0);
}

int abs(int x)
{
	if (x<0)
		return(-x);
	return(x);
}

int cal(int tim,int from,int poi)
{
	int to,dist;
	to=way[from][poi];
	dist=dis[from][poi];
	if ((hei[tim][from]&&hei[tim][to])||(!hei[tim][from]&&!hei[tim][to]))
		return(dist);
	else if (hei[tim][from]&&!hei[tim][to])
		return(dist+abs(w[from]-w[to]));
	else// if (!hei[tim][from]&&hei[tim][to])
		return(mtoz(dist-abs(w[from]-w[to])));
}

int main(void)
{
	freopen("suika.in","r",stdin);
	freopen("suika.out","w",stdout);
	int i,n,m,x,y,cos,c,pos,minnum,temp/*,head=0,tail=0,mincost=MAXNUM,temp*/;
	bool tim;
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&hei[0][i]);
		hei[1][i]=!hei[0][i];
	}
	for (i=1;i<=n;i++)
		scanf("%d",&w[i]);
	for (i=1;i<=n;i++)
		scanf("%d",&s[i]);
	for (i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&cos);
		way[x][waynum[x]]=y;
		dis[x][waynum[x]++]=cos;
	}
/*	while (tail<=head)
	{
		if (!stay[que[tail]])
		{
			head++;
			que[head]=que[tail];
			tim[head]=!tim[tail];
			cost[head]=cost[tail]+s[que[tail]];
			stay[que[tail]]=true;
		}
		for (i=0;i<waynum[que[tail]];i++)
		{
			if (!used[way[que[tail]][i]])
			{
				head++;
				que[head]=way[que[tail]][i];
				tim[head]=!tim[tail];
				if ((hei[tim[tail]][que[tail]]&&hei[tim[tail]][way[que[tail]][i]])||(!hei[tim[tail]][que[tail]]&&!hei[tim[tail]][way[que[tail]][i]]))
				{
					temp=dis[que[tail]][i];
				}
				else if (hei[tim[tail]][que[tail]]&&!hei[tim[tail]][way[que[tail]][i]])
				{
					temp=dis[que[tail]][i]+wc[que[tail]][way[que[tail]][i]];
				}
				else// if (!hei[tim[tail]][que[tail]]&&hei[tim[tail]][way[que[tail]][i]])
				{
					temp=mtoz(dis[que[tail]][i]-wc[que[tail]][way[que[tail]][i]]);
				}
				cost[head]=cost[tail]+temp;
				used[way[que[tail]][i]]=true;
				if (que[head]==n)
				{
					
				}
			}
		}
		tail++;
	}
*/
	for (i=1;i<=n;i++)
	{
		f[0][i]=MAXNUM;
		f[1][i]=MAXNUM;
	}
	f[0][1]=0;
	c=2*n;
	while (c)
	{
		minnum=MAXNUM;
		for (i=1;i<=n;i++)
		{
			if (!used[0][i]&&minnum>f[0][i])
			{
				minnum=f[0][i];
				pos=i;
				tim=0;
			}
			if (!used[1][i]&&minnum>f[1][i])
			{
				minnum=f[1][i];
				pos=i;
				tim=1;
			}
		}
		used[tim][pos]=true;
		c--;
		if (f[!tim][pos]>f[tim][pos]+s[pos])
			f[!tim][pos]=f[tim][pos]+s[pos];
		for (i=0;i<waynum[pos];i++)
		{
			temp=f[tim][pos]+cal(tim,pos,i);
			if (f[!tim][way[pos][i]]>temp)
				f[!tim][way[pos][i]]=temp;
		}
	}
	minnum=f[0][n];
	if (minnum>f[1][n])
		minnum=f[1][n];
	printf("%d\n",minnum);
	return(0);
}