记录编号	451711	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.211 s
提交时间	2017-09-18 10:04:05	内存使用	17.86 MiB

#include<bits/stdc++.h>
#define v e1[i].to
#define V e2[i].to
using namespace std;
const int max_n=100005,max_m=500005;
int n,m,tot1,tot2,fi1[max_n],fi2[max_n],w[max_n],f1[max_n],f2[max_n],vis[max_n];
struct edge{
	int to,next;
}e1[max_m*2],e2[max_m*2];
void edge_add1(int x,int y){
	e1[++tot1].to=y;
	e1[tot1].next=fi1[x];
	fi1[x]=tot1;
}
void edge_add2(int x,int y){
	e2[++tot2].to=y;
	e2[tot2].next=fi2[x];
	fi2[x]=tot2;
}
int main()
{
	freopen("trade.in","r",stdin);
	freopen("trade.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&w[i]),f1[i]=w[i],f2[i]=w[i];
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		if(z==1){
			edge_add1(x,y);
			edge_add2(y,x);
		}
		else {
			edge_add1(x,y);edge_add1(y,x);
			edge_add2(x,y);edge_add2(y,x);
		}
	}
	queue<int>S;
	S.push(1);
	memset(f1,0x3f,sizeof(f1));
	memset(f2,-0x3f,sizeof(f2));
	while(!S.empty()){
		int u=S.front();
		S.pop();
		for(int i=fi1[u];i;i=e1[i].next){
			if(!vis[v]){
				vis[v]=1;
				f1[v]=min(w[v],f1[u]);
				S.push(v);
			}
			else if(f1[v]>f1[u]){
				f1[v]=f1[u];
				S.push(v);
			}
		}
	}
	memset(vis,0,sizeof(vis));
	S.push(n);
	while(!S.empty()){
		int u=S.front();
		S.pop();
		for(int i=fi2[u];i;i=e2[i].next){
			if(!vis[V]){
				vis[V]=1;
				f2[V]=max(w[V],f2[u]);
				S.push(V);
			}
			else if(f2[V]<f2[u]){
				f2[V]=f2[u];
				S.push(V);
			}
		}
	}
	int ma=0;
	for(int i=1;i<=n;i++)ma=max(ma,f2[i]-f1[i]);
	cout<<ma;
	return 0;
}