记录编号	135994	评测结果	AAAAAAAAAA
题目名称	[東方S2] 伊吹萃香	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.060 s
提交时间	2014-11-02 08:16:09	内存使用	0.83 MiB

/*
AiKy
suika!!!!!呜哇！！！！！
*/
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int qwq=0x7fffffff;
bool flag[2][5001]={0},flag2[5001]={0};
int m[5001]={0},xt[5001]={0},head[5001]={0},to[40000]={0},ne[40000]={0},w[40000]={0},rew[40000]={0},zui[2][5001]={0};
int i,j=0,p,zj1,zj2,zj3,n,s,ans;
int ABS(int x){if(x<0)return -x;return x;}
int MIN(int x,int y){if(x<y)return x;return y;}
queue<int> A,B;
void init()
{
	scanf("%d%d",&n,&s);
	for(i=1;i<=n;i++)scanf("%d",&flag2[i]);
	for(i=1;i<=n;i++)scanf("%d",&m[i]);
	for(i=1;i<=n;i++)scanf("%d",&xt[i]);
	for(i=1;i<=s;i++)
	{
		scanf("%d%d%d",&zj1,&zj2,&zj3);
		to[i]=zj2;
		ne[i]=head[zj1];
		head[zj1]=i;
		w[i]=zj3;
		rew[i]=zj3;
		if(flag2[zj1]&&!flag2[zj2])
		{
			w[i]+=ABS(m[zj1]-m[zj2]);
			rew[i]-=ABS(m[zj1]-m[zj2]);
		}
		else if(flag2[zj2]&&!flag2[zj1])
		{
			w[i]-=ABS(m[zj1]-m[zj2]);
			rew[i]+=ABS(m[zj1]-m[zj2]);
		}
		if(w[i]<0)w[i]=0;
  		if(rew[i]<0)rew[i]=0;
	}
	j=s;
	for(i=1;i<=n;i++)
	{
		to[++j]=i;
		ne[j]=head[i];
		head[i]=j;
		if(flag2[i])w[j]=xt[i],rew[j]=0;
		else rew[j]=xt[i],w[j]=0;
	}
}
void SPFA()
{
	for(i=1;i<=n;i++)zui[0][i]=qwq,zui[1][i]=qwq;
	zui[0][1]=0;
	A.push(1);
	B.push(0);
	flag[0][1]=true;
	while(!A.empty())
	{
		zj1=A.front();A.pop();
		zj2=B.front();B.pop();
		flag[zj2][zj1]=false;
		if(zj2==0)
		for(i=head[zj1];i;i=ne[i])
		{
			zj3=zui[0][zj1]+w[i];
			if(zj3<0)zj3=0;
			if(zj3<zui[1][ to[i] ])
			{
				zui[1][ to[i] ]=zj3;
				if(!flag[1][ to[i] ])
				{
					A.push(to[i]);
					B.push(1);
					flag[1][ to[i] ]=true;
				}
			}
		}
		else
		for(i=head[zj1];i;i=ne[i])
		{
			zj3=zui[1][zj1]+rew[i];
			if(zj3<0)zj3=0;
			if(zj3<zui[0][ to[i] ])
			{
				zui[0][ to[i] ]=zj3;
				if(!flag[0][ to[i] ])
				{
					A.push(to[i]);
					B.push(0);
					flag[0][ to[i] ]=true;
				}
			}
		}
	}
}
int main()
{
	////v////suika
	freopen("suika.in","r",stdin);
	freopen("suika.out","w",stdout);
	init();
	SPFA();
	ans=MIN(zui[0][n],zui[1][n]);
	printf("%d\n",ans);
	return 0;
}