记录编号	443187	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	Hyoi_iostream	是否通过	通过
代码语言	C++	运行时间	0.214 s
提交时间	2017-08-29 20:10:37	内存使用	14.14 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;
const int MAXN = 500000;
int n,m,e = 1,ans,head[MAXN][2],MAX[MAXN],MIN[MAXN],Data[MAXN];
bool inq[MAXN];
queue<int>q;
struct node{
    int v,next;
}edge[MAXN];
inline void addedge(int u,int v){
    edge[e].next = head[u][0];edge[e].v = v;head[u][0] = e++;
    edge[e].next = head[v][1];edge[e].v = u;head[v][1] = e++;
}
inline void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&Data[i]),MIN[i]=105;
    int u,v,k;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&k);
        addedge(u,v);
        if(k==2) addedge(v,u);
    }
}

inline void spfa_1(){
    q.push(1);inq[1]=true;
    MIN[1]=Data[1];
    while(!q.empty()){
        int x=q.front();q.pop();
        inq[x]=false;
        for(int i=head[x][0];i;i=edge[i].next){
            int v=edge[i].v;
            if(MIN[v]>MIN[x]||MIN[v]>Data[v]){
               MIN[v]=min(MIN[x],Data[v]);
               if(!inq[v]) q.push(v),inq[v]=true;
            }
        }
    }

}

inline void spfa_2(){
    q.push(n);inq[n]=true;
    MAX[n]=Data[n];ans=max(ans,MAX[n]-MIN[n]);
    while(!q.empty()){
        int x=q.front();q.pop();
        inq[x]=false;

        for(int i=head[x][1];i;i=edge[i].next){
            int v=edge[i].v;
            if(MAX[v]<MAX[x]||MAX[v]<Data[v]){
               MAX[v]=max(MAX[x],Data[v]);
               ans=max(MAX[v]-MIN[v],ans);
               if(!inq[v]) q.push(v),inq[v]=true;
            }
        }
    } 
}

int main(){
	freopen("trade.in","r",stdin);
	freopen("trade.out","w",stdout); 
    init();
    spfa_1();
    memset(inq,0,sizeof(inq));
    spfa_2();
    printf("%d\n",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}