记录编号	144229	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	0.308 s
提交时间	2014-12-21 15:20:50	内存使用	3.37 MiB

#include<cstdio>
#include<vector>
#include<algorithm>
#include<deque>
#include<cstring>
using namespace std;
int F[100005];
int MAXF[100005];
int MINF[100005];
vector<int> Adj1[100005];//正图
vector<int> Adj2[100005];//反图
int n,m,ANS=0;
void Fbfs()//从n到1做bfs，中间注意Relax
{
	int temp,i,P;deque<int> Q;
	Q.push_back(n);
	while(!Q.empty())
	{
		temp=Q.at(0);MAXF[temp]=max(MAXF[temp],F[temp]);Q.pop_front();
		for(i=0;i<Adj2[temp].size();i++)
		{
			P=Adj2[temp][i];
			if(MAXF[P]<MAXF[temp])
			{
				MAXF[P]=MAXF[temp];
				Q.push_back(P);
			}
		}
	}
}
void Sbfs()//从1到n做bfs，这次需要求到各点的最小值
{
	int temp,i,P;deque<int> Q;
	Q.push_back(1);
	while(!Q.empty())
	{
		temp=Q.at(0);MINF[temp]=min(MINF[temp],F[temp]);Q.pop_front();
		for(i=0;i<Adj1[temp].size();i++)
		{
			P=Adj1[temp][i];
			if(MINF[temp]<MINF[P])
			{
				MINF[P]=MINF[temp];
				Q.push_back(P);
			}
		}
	}
}
int main()
{
	freopen("trade.in","r",stdin);
	freopen("trade.out","w",stdout);
	int i,x,y,z,temp;
	memset(MAXF,0,sizeof(MAXF));
	memset(MINF,63,sizeof(MINF));
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
		scanf("%d",&F[i]);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		if(z==1) {Adj1[x].push_back(y);Adj2[y].push_back(x);}
		else {Adj1[x].push_back(y);Adj2[x].push_back(y);Adj1[y].push_back(x);Adj2[y].push_back(x);}
	}
	Fbfs();Sbfs();
	for(i=1;i<=n;i++)
	{
		temp=MAXF[i]-MINF[i];
		ANS=max(ANS,temp);
	}
	printf("%d\n",ANS);
	return 0;
}