RT

70pts已经改不动了

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=5e6+10;
int m,n;
int dfn[N],low[N],stk[N],tag[N],vis[N];
int l[N],r[N],ans[N];
int tim,cnt,tot,top;
struct node{
    int u,v,ne;
}e[M<<1],ee[M<<1];
int h[N];
void add(int x,int y){
    e[++cnt].u=x,e[cnt].v=y,e[cnt].ne=h[x],h[x]=cnt;
}
int max(int a,int b){
    return a>b?a:b;
}
int min(int a,int b){
    return a<b?a:b;
}
void tarjan(int x){
    dfn[x]=low[x]=++tim;
    stk[++top]=x;
    vis[x]=1;
    for(int i=h[x];i;i=e[i].ne){
        int y=e[i].v;
        if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}
        else if(vis[y])low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        int now;
        while(now=stk[top--]){
            vis[now]=0;
            tag[now]=x;
            if(now==x)break;
            l[x]=min(l[x],l[now]);
            r[x]=max(r[x],r[now]);
        }
    }
}
void dfs(int x,int fa){
    ans[1]=r[1]-l[1];
    for(int i=h[x];i;i=ee[i].ne){
        int y=ee[i].v;
        if(y!=fa){
            ans[y]=max(ans[y],max(max(ans[x],r[y]-l[x]),r[y]-l[y]));
            l[y]=min(l[x],l[y]);
            dfs(y,x);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    int tmp;
    for(int i=1;i<=n;i++){
        scanf("%d",&tmp);
        l[i]=r[i]=tmp;
    }
    int x,y,z;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y);
        if(z==2)add(y,x);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }
    if(tag[1]==tag[n]){
        printf("%d",r[1]-l[1]);
        return 0;   
    }
    memset(h,0,sizeof(h));
    for(int i=1;i<=cnt;i++){
        int x=tag[e[i].u],y=tag[e[i].v];
        if(x!=y){
            ee[++tot].u=x;
            ee[tot].v=y;
            ee[tot].ne=h[x];
            h[x]=tot;
        }
    }
    dfs(1,0);
    int maxx=0;
    printf("%d",ans[tag[n]]);
    return 0;
}