神奇的bfs证联通，然后贪心求 每一种可能路径上的差值，最后求结果
#include<cstdio> #include<cstdlib> #include<queue> #include<algorithm> using namespace std; int n,m; const int N=100003,M=500003; int val[N]; int tot[2],head[2][N]; int ev[2][M<<1],enx[2][M<<1]; void add(int u,int v,int k) { ev[k][++tot[k]]=v,enx[k][tot[k]]=head[k][u],head[k][u]=tot[k]; } bool link[2][N]; void bfs(int k,int st) { queue <int> q; q.push(st),link[k][st]=true; while(!q.empty() ) { int nw=q.front() ;q.pop() ; for(int i=head[k][nw];i;i=enx[k][i]) { int nx=ev[k][i]; if(!link[k][nx] ) link[k][nx]=true,q.push(nx); } } } int d[N],mx[2][N]; bool cmp(int a,int b) { return val[a]<val[b]; } void get_ans(int k,int st,int v) { mx[k][st]=v; queue <int> q; q.push(st); while(!q.empty() ) { int nw=q.front() ;q.pop() ; for(int i=head[k][nw];i;i=enx[k][i]) { int nx=ev[k][i]; if(!mx[k][nx] && link[k^1][nx] ) mx[k][nx]=v,q.push(nx); } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++ ) scanf("%d",&val[i]),d[i]=i; while(m--) { int qa,u,v; scanf("%d%d%d",&u,&v,&qa ); add(u,v,0),add(v,u,1); if(qa==2 ) add(v,u,0),add(u,v,1); } bfs(0,1),bfs(1,n); sort(d+1,d+n+1,cmp); for(int i=1;i<=n;i++) if(link[0][d[i]] && link[1][d[i]] && !mx[0][d[i]] ) get_ans(0,d[i],val[d[i]]); for(int i=n;i>0;i--) if(link[0][d[i]] && link[1][d[i]] && !mx[1][d[i]] ) get_ans(1,d[i],val[d[i]]); int ans=0; for(int i=1;i<=n;i++) if(link[0][i] && link[1][i] ) ans=max(ans,mx[1][i]-mx[0][i] ); printf("%d ",ans); return 0; }