记录编号	461182	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	FFF团	是否通过	通过
代码语言	C++	运行时间	0.228 s
提交时间	2017-10-19 14:54:10	内存使用	6.90 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
using namespace std;
const int INF=0x7fffffff;
vector<int>g[100005];
vector<int>r[100005];
vector<int>newg[100005];
vector<int>newr[100005];
vector<int>tuopu;
stack<int>sta;
bool vis[100005];
int w[100005],belong[100005],minw[100005],maxw[100005],newin[100005];
inline void dfs1(int x){
	int l=g[x].size();
	for(register int i=0;i<l;i++)
	if(!vis[g[x][i]])
	vis[g[x][i]]=1,dfs1(g[x][i]);			
	sta.push(x);
}
inline void dfs2(int x,int cnt){
	int l=r[x].size();
	for(register int i=0;i<l;i++)
	if(!belong[r[x][i]])
	belong[r[x][i]]=cnt,dfs2(r[x][i],cnt);
}
inline void qtuopu(int x){
	vis[x]=1;
	int l=newg[x].size();
	for(int i=0;i<l;i++){
		int v=newg[x][i];
		if(!vis[v])qtuopu(v);
	}
	sta.push(x);
}
int n,m,cnt,ans;
inline void work(){
	int _min[100005],_max[100005];
	fill(_min+1,_min+cnt+1,INF);
	fill(_max+1,_max+cnt+1,0);
	for(int i=1;i<=cnt;i++)if(!newin[i])qtuopu(i);
	stack<int>sta2;
	while(sta.top()!=belong[1])sta2.push(sta.top()),sta.pop();
	_min[belong[1]]=minw[belong[1]];
	while(!sta.empty()){
		int u=sta.top();sta.pop();sta2.push(u);
		int l2=newg[u].size();
		for(int j=0;j<l2;j++){
			int v=newg[u][j];
			_min[v]=min(_min[u],minw[v]);
		}
	}
	while(sta2.top()!=belong[n])sta2.pop();
	_max[belong[n]]=maxw[belong[n]];
	while(!sta2.empty()){
		int u=sta2.top();sta2.pop();
		int l2=newr[u].size();
		for(int j=0;j<l2;j++){
			int v=newr[u][j];
			_max[v]=max(_max[u],maxw[v]);
		}
	}
	for(int i=1;i<=cnt;++i)
	ans=max(ans,_max[i]-_min[i]);
}
inline void in(int &x){
	int c=getchar();x=0;
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
}
int main(){
	freopen("trade.in","r",stdin);
	freopen("trade.out","w",stdout);
	in(n);in(m);
	for(int i=1;i<=n;++i)in(w[i]);
	int x,y,z;
	for(int i=1;i<=m;++i){
		in(x);in(y);in(z);
		if(z==1){
			g[x].push_back(y);
			r[y].push_back(x);
		}
		else {
			g[x].push_back(y);
			g[y].push_back(x);
			r[y].push_back(x);
			r[x].push_back(y);
		}
	} 
	for(int i=1;i<=n;++i)
	if(!vis[i])dfs1(i);
	while(!sta.empty()){
		int u=sta.top();sta.pop();
		if(!belong[u])belong[u]=++cnt,dfs2(u,cnt);
	}
	fill(minw+1,minw+cnt+1,INF);
	for(int i=1;i<=n;i++){
		int l=g[i].size();
		maxw[belong[i]]=max(maxw[belong[i]],w[i]);
		minw[belong[i]]=min(minw[belong[i]],w[i]);
		for(int j=0;j<l;j++){
			int v=g[i][j];
			if(belong[v]!=belong[i]){
				newin[belong[v]]++;
				newg[belong[i]].push_back(belong[v]);
				newr[belong[v]].push_back(belong[i]);
			}
			
		}
	}
	fill(vis+1,vis+cnt+1,0);
	work();
	printf("%d",ans);
	return 0;
}