P1073 最优贸易

明明每个点都通过，怎么才60分？？？

[codec]

#include<cstring>
#include<cstdio>
using namespace std;
struct tree{tree* n;int d;};
typedef tree* node;
node a[100001],a_[100001],b[100001],b_[100001];
int n,m,i,j,x,y,k;bool c[100001],c_[100001];
bool bb;int Max[100001],Min[100001],d[100001];node l,r,s;
void add(int x,int y){
    if(c[x]){b[x]->d=y;b[x]->n=new(tree);b[x]=b[x]->n;b[x]->n=NULL;b[x]->d=-1;}
    else{a[x]=new(tree);a[x]->d=y;a[x]->n=new(tree);b[x]=a[x]->n;b[x]->n=NULL;b[x]->d=-1;}
    c[x]=true;
}
void add_(int x,int y){
    if(c_[x]){b_[x]->d=y;b_[x]->n=new(tree);b_[x]=b_[x]->n;b_[x]->n=NULL;b_[x]->d=-1;}
    else{a_[x]=new(tree);a_[x]->d=y;a_[x]->n=new(tree);b_[x]=a_[x]->n;b_[x]->n=NULL;b_[x]->d=-1;}
    c_[x]=true;
}
int main()
{
    scanf("%d%d",&n,&m);for(i=1;i<=n;i++)a[i]=NULL;
    for(i=1;i<=n;i++)scanf("%d",&d[i]);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&k);
        if(k<2)add(x,y);else{add(x,y);add(y,x);}
        if(k<2)add_(y,x);else{add_(y,x);add_(x,y);}
    }
    l=new(tree);r=l;l->n=NULL;l->d=1;bb=true;memset(Min,1,sizeof(Min));Min[1]=d[1];
    while(bb){
        s=a[l->d];
        if(s!=NULL)
        while(s->d!=-1){
            if((Min[s->d]>d[s->d])||(Min[s->d]>Min[l->d])){
                r->n=new(tree);r=r->n;r->d=s->d;r->n=NULL;
                if(d[s->d]>Min[l->d])Min[s->d]=Min[l->d];else Min[s->d]=d[s->d];
            }
            s=s->n;
        }
        if(l==r)bb=false;else{s=l->n;delete(l);l=s;}
    }
    delete(l);
    l=new(tree);r=l;l->n=NULL;l->d=n;bb=true;memset(Max,0,sizeof(Max));Max[n]=d[n];
    while(bb){
        s=a_[l->d];
        if(s!=NULL)
        while(s->d!=-1){
            if((Max[s->d]<d[s->d])||(Max[s->d]<Max[l->d])){
                r->n=new(tree);r=r->n;r->d=s->d;r->n=NULL;
                if(d[s->d]<Max[l->d])Max[s->d]=Max[l->d];else Max[s->d]=d[s->d];
            }
            s=s->n;
        }
        if(l==r)bb=false;else{s=l->n;delete(l);l=s;}
    };delete(l);k=0;
    for(i=1;i<=n;i++)if(Max[i]-Min[i]>k)k=Max[i]-Min[i];
    printf("%d\n",k);
    return 0;
}

[/codec]