记录编号	501329	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	0.596 s
提交时间	2018-07-20 23:27:43	内存使用	3.84 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
vector<int>a[100001],b[100001];
priority_queue<pair <int,int> > q;
int n,m,f[100001],a1,a2,a3,d1[100001],d2[100001],x,y,z,ma=0;
bool ju[100001];
int main(){
    freopen("trade.in","r",stdin);
    freopen("trade.out","w",stdout);
    cin>>n>>m;
    if(n<=2){
	    cout<<0;
	    return 0;
	}
    for(int i=1;i<=n;i++)d2[i]=9999999;
    for(int i=1;i<=n;i++)cin>>f[i];
    for(int i=1;i<=m;i++){
    	cin>>a1>>a2>>a3;
    	a[a1].push_back(a2);
    	b[a2].push_back(a1);
    	if(a3==2){
        	a[a2].push_back(a1);
    	    b[a1].push_back(a2);		
    	}
	}
	d1[n]=f[n];
	q.push(make_pair(d1[n],n));
	while(q.size()){
		x=q.top().second;q.pop();
		if(ju[x])continue;
		ju[x]=1;
		for(int i=0;i<b[x].size();i++){
			y=b[x][i];z=f[y];
			if(!ju[y]){
				d1[y]=max(d1[x],z);
				q.push(make_pair(d1[y],y));
			}
		}
	}
	for(int i=1;i<=n;i++)ju[i]=0;
	d2[1]=f[1];
	q.push(make_pair(-d2[1],1));
	while(q.size()){
		x=q.top().second;q.pop();
		if(ju[x])continue;
		ju[x]=1;
		for(int i=0;i<a[x].size();i++){
			y=a[x][i];z=f[y];
			if(!ju[y]){
				d2[y]=min(d2[x],z);
				q.push(make_pair(-d2[y],y));
			}
		}
	}
	for(int i=2;i<n;i++){
		ma=max(ma,d1[i]-d2[i]);
    }
    cout<<ma;
    return 0;
}
/*
6 6
100 64 47 50 57 1
1 2 1
2 3 1
1 3 1
1 4 1
1 5 1
5 6 1

0
*/