提交时间:2024-12-12 17:22:48
运行 ID: 314209
#include<bits/stdc++.h> using namespace std; int a[100002]; vector<int>b[100002]; int n,m,sum; void abc(int x,int y,int z) { if(x==n) { sum=max(sum,y); return ; } for(int i=0; i<b[x].size(); i++) { if(a[b[x][i]]<z) { abc(b[x][i],y,a[b[x][i]]); } else { if(a[b[x][i]]-z>y) { abc(b[x][i],a[b[x][i]]-z,z); } } } } int main() { cin>>n>>m; for(int i=1; i<=n; i++) { cin>>a[i]; } int d1,d2,z; for(int i=1; i<=m; i++) { cin>>d1>>d2>>z; b[d1].push_back(d2); } abc(1,0,a[1]); cout<<sum; return 0; }