记录编号	428721	评测结果	AAAAAAAAAA
题目名称	[東方S2] 伊吹萃香	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	0.069 s
提交时间	2017-07-26 07:39:35	内存使用	0.78 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
#define maxn 5005
#define maxx 30005
#define mem(a,b) memset(a,b,sizeof(a))
#define nd(x,y)((col[x]^y)?str[x]:0)
using namespace std;
int n,m,col[maxn],wei[maxn],str[maxn],dis[maxn][2],num,hea[maxn];
bool ok[maxn][2];
struct road{int en,nex,w;}ro[maxx];
void add(int x,int y,int z){ro[num].en=y;ro[num].w=z;ro[num].nex=hea[x];hea[x]=num++;}
inline int read()
{
	int x=0,y=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-') y=-1; c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*y;
}
void spfa()
{
	queue<pair<int,int> >q;
	mem(dis,0x7f);
	dis[1][0]=0;ok[1][0]=1;q.push(make_pair(1,0));
	if(col[1]) dis[1][1]=str[1]; else dis[1][1]=0;
	ok[1][1]=1;q.push(make_pair(1,1));
	while(!q.empty())
	{
		int u=q.front().first,st=q.front().second;q.pop();ok[u][st]=0;
		if(dis[u][st^1]>dis[u][st]+nd(u,st))
		{
			dis[u][st^1]=dis[u][st]+nd(u,st);
			if(!ok[u][st^1]) q.push(make_pair(u,st^1)),ok[u][st^1]=1;
		}
		for(int i=hea[u];i!=-1;i=ro[i].nex)
		{
			int v=ro[i].en;
			if(col[u]!=col[v])
			{	
				int delta=(col[v]^st)?(-abs(wei[u]-wei[v])):abs(wei[u]-wei[v]);
				if(dis[v][st^1]>dis[u][st]+max(ro[i].w+delta,0))
				{
					dis[v][st^1]=dis[u][st]+max(ro[i].w+delta,0);
					if(!ok[v][st^1]) q.push(make_pair(v,st^1)),ok[v][st^1]=1;
				}
			}
			else if(dis[v][st^1]>dis[u][st]+ro[i].w)
				 {
				    dis[v][st^1]=dis[u][st]+ro[i].w;
					if(!ok[v][st^1]) q.push(make_pair(v,st^1)),ok[v][st^1]=1;
				 }
		}
	}
}
int main()
{
	freopen("suika.in","r",stdin);
	freopen("suika.out","w",stdout);
	mem(hea,-1);
	n=read();m=read();int x,y,z;
	for(int i=1;i<=n;i++) col[i]=read();
	for(int i=1;i<=n;i++) wei[i]=read();
	for(int i=1;i<=n;i++) str[i]=read();
	for(int i=1;i<=m;i++)
		x=read(),y=read(),z=read(),add(x,y,z);
	spfa();
	printf("%d",min(dis[n][0],dis[n][1]));
	return 0;
}