记录编号	409689	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	Menamovic	是否通过	通过
代码语言	C++	运行时间	0.275 s
提交时间	2017-05-28 20:57:47	内存使用	3.74 MiB

#include<cstdio>
#include<vector>
#include<cstring>
#include<deque>
#include<algorithm>

using namespace std;

const int MC=100000+5;

int F[MC];
int MAXN[MC];
int MINN[MC];
vector<int> ADJ1[MC];
vector<int> ADJ2[MC];
int n,m;
int ans;

void tbfs()
{
	int temp,P;
	deque<int> Q;
	Q.push_back(1);
	while(!Q.empty())
	{
		temp=Q.at(0);MINN[temp]=min(MINN[temp],F[temp]);Q.pop_front();
		for(int i=0;i<ADJ1[temp].size();i++)
		{
			P=ADJ1[temp][i];
			if(MINN[P]>MINN[temp])
			{
				MINN[P]=MINN[temp];
				Q.push_back(P);
			}
		}
	}
}

void fbfs()
{
	int temp,P;
	deque<int> Q;
	Q.push_back(n);
	while(!Q.empty())
	{
		temp=Q.at(0);MAXN[temp]=max(MAXN[temp],F[temp]);Q.pop_front();
		for(int i=0;i<ADJ2[temp].size();i++)
		{
			P=ADJ2[temp][i];
			if(MAXN[P]<MAXN[temp])
			{
				MAXN[P]=MAXN[temp];
				Q.push_back(P);
			}
		}
	}
}

int main()
{
	freopen("trade.in","r",stdin);
	freopen("trade.out","w",stdout);
	int x,y,z,temp;
	memset(MAXN,0,sizeof(MAXN));
	memset(MINN,63,sizeof(MINN));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&F[i]);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		ADJ1[x].push_back(y);ADJ2[y].push_back(x);
		if(z!=1)
		{
			ADJ1[y].push_back(x);
			ADJ2[x].push_back(y);
		}
	}
	tbfs();
	fbfs();
	for(int i=1;i<=n;i++)
	{
		temp=MAXN[i]-MINN[i];
		ans=max(ans,temp);
	}
	printf("%d",ans);
	return 0;
}