记录编号	443146	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	Hyoi_0Koto	是否通过	通过
代码语言	C++	运行时间	0.144 s
提交时间	2017-08-29 19:17:54	内存使用	2.05 MiB

#prag\
ma GCC optimize("O3")
#include<cstdio>
#include<cctype>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define loop(i,j,k) for(int i=j;i<=k;i++)
#define smax(a,b) a>b?a:b
#define smin(a,b) a<b?a:b
using namespace std;
inline void in(int &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while (isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=f;
}
inline void out(int x){
    if(!x){putchar('0');return;}
    if(x<0)x=~x+1,putchar('-');
    char c[30]={0};
    while(x)c[++c[0]]=x%10+48,x/=10;
    while(c[0])putchar(c[c[0]--]);
}
const int maxn=100001;
const int inf=101;
int n,m,x,y,z,ans;
int p[maxn],d1[maxn],d2[maxn];
vector<int> g1[maxn],g2[maxn];
queue<int> q;
bool inq[maxn];
inline void bf_spfa1(){
	fill(d1+1,d1+n+1,inf);
	inq[1]=1;q.push(1);d1[1]=p[1];
	while(!q.empty()){
		int u=q.front();q.pop();inq[u]=0;
		for(int i=0;i<g1[u].size();i++){
			int v=g1[u][i];
			if(d1[v]>d1[u]){
				d1[v]=d1[u];
				if(!inq[v]) inq[v]=1,q.push(v);
			}
			if(p[v]<d1[v]){
				d1[v]=p[v];
				if(!inq[v]) inq[v]=1,q.push(v);
			}
		}
	}
}
inline void bf_spfa2(){
	inq[n]=1;q.push(n);d2[n]=p[n];
	while(!q.empty()){
		int u=q.front();q.pop();inq[u]=0;
		for(int i=0;i<g2[u].size();i++){
			int v=g2[u][i];
			if(d2[v]<d2[u]){
				d2[v]=d2[u];
				if(!inq[v]) inq[v]=1,q.push(v);
			}
			if(p[v]>d2[v]){
				d2[v]=p[v];
				if(!inq[v]) inq[v]=1,q.push(v);
			}
		}
	}
}
inline int poi(){
	freopen("trade.in","r",stdin);
	freopen("trade.out","w",stdout);
	in(n);in(m);
	loop(i,1,n)in(p[i]);
	loop(i,1,m){
		in(x);in(y);in(z);
		g1[x].push_back(y);g2[y].push_back(x);
		if(!(z-2)){
			g1[y].push_back(x);g2[x].push_back(y);
		}
	}
	bf_spfa1();
	bf_spfa2();
	loop(i,1,n) ans=smax(ans,d2[i]-d1[i]);
	out(ans);
}
int yuudachi=poi();
int main(){;}