记录编号	324417	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	Metatron	是否通过	通过
代码语言	C++	运行时间	0.201 s
提交时间	2016-10-18 08:17:41	内存使用	6.41 MiB

#include<cstdio>
#include<cstring>
#include<deque>
const int maxn=100005,maxm=500005;
using namespace std;
struct Edge{
	int next,to;
}a[maxm+maxn];
int n,m,len,data[maxn],dis1[maxn],dis2[maxn],head[maxn];
void Insert(int x,int y){
	a[++len].next=head[x];a[len].to=y;head[x]=len;
}
void spfa1(){
	bool f[maxn]={0};
	memset(dis1,0xc2,sizeof dis1);
	deque<int>q;
	q.push_front(1);dis1[1]=data[1]-dis2[1];f[1]=1;
	while(!q.empty()){
		int x=q.front();q.pop_front();f[x]=0;
		for(int i=head[x];i!=-1;i=a[i].next){
			int k=a[i].to;
			if(dis1[k]<max(dis1[x],data[k]-dis2[k])){
				dis1[k]=max(dis1[x],data[k]-dis2[k]);//printf("%d %d\n",k,dis1[k]);
				if(!f[k]){
					f[k]=1;
					if(!q.empty() && dis1[q.front()]<dis1[k])	q.push_front(k);
					else q.push_back(k);
				}
			}
		}
	}
}
void spfa2(){
	memset(dis2,0x3f,sizeof dis2);
	bool f[maxn]={0};deque<int>q;
	dis2[1]=data[1];f[1]=1;q.push_front(1);
	while(!q.empty()){
		int x=q.front();q.pop_front();f[x]=0;
		for(int i=head[x];i!=-1;i=a[i].next){
			int k=a[i].to;
			if(dis2[k]>min(dis2[x],data[k])){
				dis2[k]=min(dis2[x],data[k]);
				if(!f[k]){
					f[k]=1;
					if(!q.empty() && dis2[q.front()]>dis2[k])	q.push_front(k);
					else q.push_back(k);
				}
			}
		}
	}
}
int main(){
	freopen("trade.in", "r", stdin);
    freopen("trade.out", "w", stdout);
	memset(head,-1,sizeof head);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&data[i]);
	for(int i=1;i<=m;++i){
		int x,y,t;
		scanf("%d%d%d",&x,&y,&t);
		if(t==1)	Insert(x,y);
		else{
			Insert(y,x);
			Insert(x,y);
		}
	}
	//
	spfa2();spfa1();
	int tmp=0;
	/*for(int i=1;i<=n;++i)
		if(tmp<data[i]-dis2[n])	tmp=data[i]-dis2[n];*/
	printf("%d\n",dis1[n]);
	//while(9);
	return 0;
}