提交时间:2024-12-12 16:58:12

运行 ID: 314136

#include<bits/stdc++.h> using namespace std; int n,m; int w[100002]; vector<int> g[100002]; int maxx=0; void dfs(int x,int y,int z,int vv)//这个点 上一个点 最小买入 转的最大差价 { if(x==n) { maxx=max(maxx,max(vv,w[n]-z)); return ; } for(int i=0;i<g[x].size();i++) { int u=g[x][i]; if(u!=y) { dfs(u,x,min(z,w[u]),max(vv,w[u]-z)); } } } 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 a1,a2,a3; scanf("%d%d%d",&a1,&a2,&a3); g[a1].push_back(a2); if(a3==2) { g[a2].push_back(a1); } } dfs(1,0,w[1],0); cout<<maxx<<endl; return 0; }