C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10,M=2000010;
int n,m;
int w[N];
int Min[N],Max[N];//1-k的最小值 k-n的最大值
int h[N],rh[N],e[M],ne[M],idx;
void add(int h[],int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs_h(int u,int value){//min
if(value>=Min[u]) return ;//若该点已经有较优解,则新的这个搜索分支没有必要
Min[u]=min(value,w[u]);//value 是从起点到u的上一个的点的最小值
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
dfs_h(j,Min[u]);
}
}
void dfs_rh(int u,int value){//max
if(value<=Max[u]) return ;
Max[u]=max(value,w[u]);
for(int i=rh[u];~i;i=ne[i]){
int j=e[i];
dfs_rh(j,Max[u]);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
memset(Min,0x3f,sizeof Min);
memset(h,-1,sizeof h);
memset(rh,-1,sizeof rh);
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
add(h,a,b);
add(rh,b,a);
if(c==2){
add(h,b,a);
add(rh,a,b);
}
}
dfs_h(1,w[1]);
dfs_rh(n,w[n]);
int res=0;
for(int i=1;i<=n;i++) res=max(res,Max[i]-Min[i]);
cout<<res;
return 0;
}
作者:Immerse
链接:https://www.acwing.com/activity/content/code/content/2493328/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。