记录编号	41673	评测结果	AAAAAAAAAA
题目名称	[東方S2] 伊吹萃香	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.110 s
提交时间	2012-08-08 21:40:50	内存使用	0.56 MiB

#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#define white 0
#define black 1
using namespace std;
const int MAXN=5010;
const int INF=(~0u)>>2;
typedef pair<int,int> Pair;
int N,M,color[MAXN],w[MAXN],tei[MAXN];
vector<int> map[MAXN],val[MAXN];

inline void init()
{
	scanf("%d%d\n",&N,&M);
	for(int i=1;i<=N;i++) scanf("%d",&color[i]);
	for(int i=1;i<=N;i++) scanf("%d",&w[i]);
	for(int i=1;i<=N;i++) scanf("%d",&tei[i]);
	int u,v,k; for(int i=1;i<=M;i++)
	{
		scanf("%d%d%d\n",&u,&v,&k);
		map[u].push_back(v);
		val[u].push_back(k);
	}
}

int flag[MAXN][2],dist[MAXN][2];
queue<Pair> q;

inline int myabs(int a) {return a<0?-a:a;}

inline void bfs()
{
	for(int i=1;i<=N;i++)
		flag[i][0]=0,flag[i][1]=0,
		dist[i][0]=INF,dist[i][1]=INF;
	int u,v,c,t,nt,tcu,tcv;Pair tmp;
	q.push(make_pair(1,0));
	dist[1][0]=0; flag[1][0]=1;
	while(q.size())
	{
		tmp=q.front(); q.pop(); 
		u=tmp.first,t=tmp.second; flag[u][t]=0;
		if(t==0) tcu=color[u]; else tcu=!color[u];
		nt=(t+1)%2;
		/*Stay*/ 
		if(tcu==white) c=dist[u][t];
		else c=dist[u][t]+tei[u];
		if(dist[u][nt]>c)
		{
			dist[u][nt]=c;
			if(!flag[u][nt])
			{
				flag[u][nt]=1;
				q.push(make_pair(u,nt));
			}
		}
		/*Go*/
		for(unsigned int i=0;i<map[u].size();i++)
		{
			v=map[u][i]; 
			if(tcu==color[u]) tcv=color[v];
			else tcv=!color[v];
			c=val[u][i];
			if(tcu==white && tcv==black)
			{	
				c-=myabs(w[u]-w[v]);
				if(c<0) c=0;
			}
			if(tcu==black && tcv==white)
				c+=myabs(w[u]-w[v]);
			c+=dist[u][t];
			if(dist[v][nt]<=c) continue;
			dist[v][nt]=c;
			if(flag[v][nt]) continue;
			flag[v][nt]=1; q.push(make_pair(v,nt));
		}
	}
}

int main()
{
	freopen("suika.in","r",stdin);
	freopen("suika.out","w",stdout);
	init();
	bfs();
	if(dist[N][0]<=dist[N][1]) 
		printf("%d\n",dist[N][0]);
	else printf("%d\n",dist[N][1]);
	return 0;
}