#include<bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second const int B1=1e5; const int B2=1e4; int n,m; ll p[105]; vector<pair<ll,int> >out[105],in[105]; ll dp1[B1+1][105],dp2[B2+1][105]; bool vis[105]; void solve(){ cin >> n >> m; for(int i=1; i<=n ;i++){ out[i].clear(); in[i].clear(); cin >> p[i]; } for(int i=1; i<=m ;i++){ int u,v,w;cin >> u >> v >> w; out[u].push_back({w,v}); in[v].push_back({w,u}); } for(int i=1; i<=B1 ;i++){ for(int j=1; j<=n ;j++) dp1[i][j]=0; } for(int i=1; i<=B2 ;i++){ for(int j=1; j<=n ;j++) dp2[i][j]=0; } dp1[1][1]=1; for(int i=1; i<=B1 ;i++){ queue<int>q; for(int j=1; j<=n ;j++) if(dp1[i][j]) q.push(j); while(!q.empty()){ int x=q.front();q.pop(); for(auto c:out[x]){ if(c.fi*i<=B1){ int ni=i*c.fi; if(!dp1[ni][c.se] && ni<=p[c.se]){ dp1[ni][c.se]=1; if(ni==i) q.push(c.se); } } } } for(int j=1; j<=n ;j++){ if(dp1[i][j]) dp1[i][j]=i; else dp1[i][j]=dp1[i-1][j]; } } dp2[1][n]=p[n]; ll ans=(n==1); for(int i=1; i<=B2 ;i++){ typedef pair<ll,int> pli; priority_queue<pli>pq; for(int j=1; j<=n ;j++){ vis[j]=false; if(dp2[i][j]) pq.push({dp2[i][j],j}); } while(!pq.empty()){ int x=pq.top().se;pq.pop(); if(vis[x]) continue; vis[x]=true; for(auto c:in[x]){ if(c.fi*i<=B2){ int ni=c.fi*i; if(dp2[ni][c.se]<min(p[c.se],dp2[i][x]/c.fi)){ dp2[ni][c.se]=min(p[c.se],dp2[i][x]/c.fi); if(ni==i) pq.push({dp2[i][c.se],c.se}); } } { int frog=min((ll)dp2[i][x]/c.fi,(ll)B1); ans=max(ans,dp1[frog][c.se]*c.fi*i); } } } } if(ans==0) cout << "-1\n"; else cout << ans << '\n'; } int main(){ ios::sync_with_stdio(false);cin.tie(0); int t;cin >> t;while(t--) solve(); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | #include<bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second const int B1=1e5; const int B2=1e4; int n,m; ll p[105]; vector<pair<ll,int> >out[105],in[105]; ll dp1[B1+1][105],dp2[B2+1][105]; bool vis[105]; void solve(){ cin >> n >> m; for(int i=1; i<=n ;i++){ out[i].clear(); in[i].clear(); cin >> p[i]; } for(int i=1; i<=m ;i++){ int u,v,w;cin >> u >> v >> w; out[u].push_back({w,v}); in[v].push_back({w,u}); } for(int i=1; i<=B1 ;i++){ for(int j=1; j<=n ;j++) dp1[i][j]=0; } for(int i=1; i<=B2 ;i++){ for(int j=1; j<=n ;j++) dp2[i][j]=0; } dp1[1][1]=1; for(int i=1; i<=B1 ;i++){ queue<int>q; for(int j=1; j<=n ;j++) if(dp1[i][j]) q.push(j); while(!q.empty()){ int x=q.front();q.pop(); for(auto c:out[x]){ if(c.fi*i<=B1){ int ni=i*c.fi; if(!dp1[ni][c.se] && ni<=p[c.se]){ dp1[ni][c.se]=1; if(ni==i) q.push(c.se); } } } } for(int j=1; j<=n ;j++){ if(dp1[i][j]) dp1[i][j]=i; else dp1[i][j]=dp1[i-1][j]; } } dp2[1][n]=p[n]; ll ans=(n==1); for(int i=1; i<=B2 ;i++){ typedef pair<ll,int> pli; priority_queue<pli>pq; for(int j=1; j<=n ;j++){ vis[j]=false; if(dp2[i][j]) pq.push({dp2[i][j],j}); } while(!pq.empty()){ int x=pq.top().se;pq.pop(); if(vis[x]) continue; vis[x]=true; for(auto c:in[x]){ if(c.fi*i<=B2){ int ni=c.fi*i; if(dp2[ni][c.se]<min(p[c.se],dp2[i][x]/c.fi)){ dp2[ni][c.se]=min(p[c.se],dp2[i][x]/c.fi); if(ni==i) pq.push({dp2[i][c.se],c.se}); } } { int frog=min((ll)dp2[i][x]/c.fi,(ll)B1); ans=max(ans,dp1[frog][c.se]*c.fi*i); } } } } if(ans==0) cout << "-1\n"; else cout << ans << '\n'; } int main(){ ios::sync_with_stdio(false);cin.tie(0); int t;cin >> t;while(t--) solve(); } |