#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define FOR(i,l,r) for(int i = (l); i <= (r); i++) #define FORD(i,l,r) for(int i = (l); i >= (r); i--) using num = double; using ind = long long; gp_hash_table<ind,null_type> s[101]; struct edge{ ind v; ind w; }; ind n,m; vector<edge> edges[101]; ind capacity[101]; ind solve(ind v, ind k){ if(capacity[v] < k) return -1; if(s[v].find(k) != s[v].end()) return -1; s[v].insert(k); ind max_solution = -1; for(edge e : edges[v]){ max_solution = max(max_solution, solve(e.v, k*e.w)); } if(v == n) max_solution = max(max_solution, k); return max_solution; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--){ cin >> n >> m; FOR(i,1,n){ edges[i].clear(); s[i].clear(); cin >> capacity[i]; } FOR(i,1,m){ ind a,b,w; cin >> a >> b >> w; edges[a].push_back({b,w}); } cout << solve(1,1) << '\n'; } }
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 | #include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define FOR(i,l,r) for(int i = (l); i <= (r); i++) #define FORD(i,l,r) for(int i = (l); i >= (r); i--) using num = double; using ind = long long; gp_hash_table<ind,null_type> s[101]; struct edge{ ind v; ind w; }; ind n,m; vector<edge> edges[101]; ind capacity[101]; ind solve(ind v, ind k){ if(capacity[v] < k) return -1; if(s[v].find(k) != s[v].end()) return -1; s[v].insert(k); ind max_solution = -1; for(edge e : edges[v]){ max_solution = max(max_solution, solve(e.v, k*e.w)); } if(v == n) max_solution = max(max_solution, k); return max_solution; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--){ cin >> n >> m; FOR(i,1,n){ edges[i].clear(); s[i].clear(); cin >> capacity[i]; } FOR(i,1,m){ ind a,b,w; cin >> a >> b >> w; edges[a].push_back({b,w}); } cout << solve(1,1) << '\n'; } } |