#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int m,n,k,a[100100],maxx[1000100],minn[1000100],v[1010001],f[1000100],ans;
struct node{
int x,y,next,w;
}xx[10000010];
node yy[1000100];
int tot,tot1,hd1[10001000],hd[1001000];
void add1(int x,int y,int w){
tot++;
xx[tot].x=x;
xx[tot].y=y;
xx[tot].w=w;
xx[tot].next=hd[x];
hd[x]=tot;
}
void add2(int x,int y,int w){
tot1++;
yy[tot1].x=x;
yy[tot1].y=y;
yy[tot1].w=w;
yy[tot1].next=hd1[x];
hd1[x]=tot1;
}
void spfa(int x){
memset(minn,0x3f,sizeof(minn));
minn[x]=a[x];
v[x]=1;
f[1]=x;
int head=0,tail=1;
while(head!=tail){
head=head%100010+1;
int x1=f[head];
for(int i=hd[x1];i;i=xx[i].next){
if(minn[xx[i].y]>min(a[xx[i].y],minn[x1])){
minn[xx[i].y]=min(a[xx[i].y],minn[x1]);
if(v[xx[i].y]==0){
tail++;
v[xx[i].y]=1;
f[tail]=xx[i].y;
}
}
}
v[x1]=0;
}
}
void spfa1(int x){
memset(v,0,sizeof(v));
maxx[x]=a[x];
v[x]=1;
f[1]=x;
int head=0,tail=1;
while(head!=tail){
head=head%100010+1;
int x1=f[head];
for(int i=hd1[x1];i;i=yy[i].next){
if(maxx[yy[i].y]<max(a[yy[i].y],maxx[x1])){
maxx[yy[i].y]=max(a[yy[i].y],maxx[x1]);
if(v[yy[i].y]==0){
tail++;
v[yy[i].y]=1;
f[tail]=yy[i].y;
}
}
}
v[x1]=0;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
int x,y,k;
cin>>x>>y>>k;
if(k==1){
add1(x,y,a[y]);
add2(y,x,a[x]);
}
else{
add1(x,y,a[y]);
add1(y,x,a[x]);
add2(x,y,a[y]);
add2(y,x,a[x]);
}
}
spfa(1);
spfa1(n);
ans=0;
for(int i=2;i<n;i++){
ans=max(ans,maxx[i]-minn[i]);
}
cout<<ans;
}
刘子涵ssl
发布了30 篇原创文章 · 获赞 24 · 访问量 1013
私信
关注