思路：这道题的标签是SPFA，但是我觉得这道题可以用记忆化搜索，用两组dfs，将从1到 i点道路上的最小值都存进min数组，将i 到n点的最大值存进max组，最后遍历min与max两数组的最大差值，输出即可。其中借助vector容器将每个点连通的点都遍历到。
AC代码：
#include<bits/stdc++.h> using namespace std; vector<int>way_min[110000]; vector<int>way_max[110000]; int value[110000],minn[110000],maxx[110000]; void dfs_min(int x,int m) { if(m>=minn[x]) return ; m=min(m,value[x]); minn[x]=m; for(int i=0;i<way_min[x].size();i++) { dfs_min(way_min[x][i],m); } } void dfs_max(int x,int m) { if(m<=maxx[x]) return ; m=max(m,value[x]); maxx[x]=m; for(int i=0;i<way_max[x].size();i++) { dfs_max(way_max[x][i],m); } } int main() { int n,m,x,y,z,ans=0; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>value[i]; minn[i]=1000; maxx[i]=-1000; } for(int i=1;i<=m;i++) { cin>>x>>y>>z; way_min[x].push_back(y); way_max[y].push_back(x); if(z==2) { way_min[y].push_back(x); way_max[x].push_back(y); } } dfs_min(1,value[1]); dfs_max(n,value[n]); for(int i=1;i<=n;i++) ans=max(ans,maxx[i]-minn[i]); cout<<ans<<endl; return 0; }
