提交时间:2024-12-12 17:13:01
运行 ID: 314197
#include<bits/stdc++.h> using namespace std; int n,m,w[100001],maxx=-0x5f5f5f5f; vector<int>g[100001]; set<int>f[100001]; inline void dfs(int x,int yu) { f[yu].insert(x); maxx=max(maxx,w[x]-w[yu]); for(int i=0;i<g[x].size();++i) { if(f[yu].count(g[x][i])==0) { //f[yu].insert(g[x][i]); dfs(g[x][i],yu); } } } int main() { scanf("%d%d",&n,&m); for(int i=1; i<=n; ++i) { scanf("%d",&w[i]); } for(int i=1; i<=m; ++i) { int x,y,z; scanf("%d%d%d",&x,&y,&z); g[x].push_back(y); if(z==2) g[y].push_back(x); } for(int i=1;i<=n;++i) { dfs(i,i); } cout<<maxx; return 0; }