记录编号	264069	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	C++	运行时间	0.280 s
提交时间	2016-05-27 13:00:15	内存使用	8.52 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

int i,j,n,m,cnt,ans=0,d,dp,x,y,k;
bool v[100010],f[100010];
int rd[100010],rd2[100010],cmin[100010],cmax[100010]={0};
int low[100010],dfn[100010],ys[100010],z[100010],a[100010];

vector <int> l[100010],ll[100010],fl[100010];
vector <int> q[100010];

inline int min(int a,int b){return (a<b)?a:b;}
inline int max(int a,int b){return (a>b)?a:b;}

inline void work(int p){
	q[++cnt].push_back(p);
	ys[p]=cnt;
	while (z[dp]!=p) {
		ys[z[dp]]=cnt;
		q[cnt].push_back(z[dp]);
		f[z[dp]]=0;
		dp--;}
	f[z[dp]]=0;	dp--;
	return;
}

inline void tarjan(int x){
	int i;
	low[x]=dfn[x]=++d;
	f[x]=true;	z[++dp]=x;
	if (l[x].size()!=0)	
	for (i=0;i<=l[x].size()-1;i++)
	if (not v[l[x][i]])	{
		v[l[x][i]]=1;	tarjan(l[x][i]);
		low[x]=min(low[x],low[l[x][i]]);
	}	else if (f[l[x][i]]==1)	
	low[x]=min(low[x],dfn[l[x][i]]);
	if (low[x]==dfn[x])	work(x);
	return;
}

void ready(){
	int i,j,mm=0;
	for (i=1;i<=n;i++)
		if (l[i].size()!=0)
		for (j=0;j<=l[i].size()-1;j++)
		if (ys[i]!=ys[l[i][j]]){
		ll[ys[i]].push_back(ys[l[i][j]]);
		fl[ys[l[i][j]]].push_back(ys[i]);
		rd[ys[l[i][j]]]++; 
		rd2[ys[i]]++;	}
	memset(cmin,0x3f3f3f3f,sizeof(cmin));
	for (i=1;i<=n;i++)	cmax[ys[i]]=max(a[i],cmax[ys[i]]);
	for (i=1;i<=n;i++)	cmin[ys[i]]=min(a[i],cmin[ys[i]]);
	return;
}

void bfs1(){
	int i=0,t=0;
	memset(z,0,sizeof(z));
	z[++z[0]]=ys[1];	t=1;
	while (t<=z[0]) {
		if (ll[z[t]].size()!=0)	
			for (i=0;i<=ll[z[t]].size()-1;i++){
			cmin[ll[z[t]][i]]=min(cmin[ll[z[t]][i]],cmin[z[t]]);
			rd[ll[z[t]][i]]--;	if (rd[ll[z[t]][i]]==0)
			z[++z[0]]=ll[z[t]][i];		
		}
	t++; 	}
	for (i=1;i<=n;i++)
		if (l[i].size()!=0) for (j=0;j<=l[i].size()-1;j++)
		if (ys[i]!=ys[l[i][j]])
		rd[ys[l[i][j]]]++;
	return;
}

void bfs2(){
	int i=0,p=0,t=0;
	memset(z,0,sizeof(z));
		z[++z[0]]=ys[n];	t=1;	
	while (t<=z[0]) {
		if (fl[z[t]].size()!=0)	
			for (i=0;i<=fl[z[t]].size()-1;i++){
			cmax[fl[z[t]][i]]=max(cmax[fl[z[t]][i]],cmax[z[t]]);
			rd2[fl[z[t]][i]]--;	if (rd2[fl[z[t]][i]]==0) 
			z[++z[0]]=fl[z[t]][i];		
		}
	t++;	}
	return;
}

void pr(){
	int i=0,t=0;
	memset(z,0,sizeof(z));
	for (i=1;i<=n;i++)	low[ys[i]]=cmax[ys[i]]-cmin[ys[i]];
	z[++z[0]]=ys[1];	t=1;
	while (t<=z[0]) {
		if (ll[z[t]].size()!=0)	
			for (i=0;i<=ll[z[t]].size()-1;i++){
			low[ll[z[t]][i]]=max(low[ll[z[t]][i]],low[z[t]]);
			rd[ll[z[t]][i]]--;	if (rd[ll[z[t]][i]]==0)
			z[++z[0]]=ll[z[t]][i];		
		}
	t++; 	}
	printf("%d\n",low[ys[n]]);	
	return;
}

int main(){
	freopen("trade.in","r",stdin);
	freopen("trade.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++) 	scanf("%d",&a[i]);
	for (i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&k);
		l[x].push_back(y);
		if (k==2)	l[y].push_back(x);}
	for (i=1;i<=n;i++)
		if (not v[i])	{
			v[i]=true;	tarjan(i);}		
	ready();	bfs1();	bfs2();	pr();
	return 0;
}