#include <bits/stdc++.h> using namespace std; using ll = int64_t; ll bfs(int n, const vector<ll> &routers, const vector<vector<pair<int, ll>>> &graph) { queue<pair<int, ll>> q; q.emplace(0, 1); ll max_strength = -1; while (!q.empty()) { auto [node, strength] = q.front(); q.pop(); if (strength > routers[node]) continue; if (node == n - 1) { max_strength = max(max_strength, strength); } for (auto [next, weight] : graph[node]) { if (strength > LLONG_MAX / weight) continue; ll new_strength = strength * weight; if (new_strength <= routers[next]) { q.emplace(next, new_strength); } } } return max_strength; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int T; scanf("%d", &T); while (T--) { int n, m; scanf("%d %d", &n, &m); vector<ll> routers(n); for (int i = 0; i < n; i++) { scanf("%lld", &routers[i]); } vector<vector<pair<int, ll>>> graph(n); for (int i = 0; i < m; i++) { int a, b; ll w; scanf("%d %d %lld", &a, &b, &w); --a, --b; graph[a].emplace_back(b, w); } ll max_strength = bfs(n, routers, graph); printf("%lld\n", max_strength); } return 0; }
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 | #include <bits/stdc++.h> using namespace std; using ll = int64_t; ll bfs(int n, const vector<ll> &routers, const vector<vector<pair<int, ll>>> &graph) { queue<pair<int, ll>> q; q.emplace(0, 1); ll max_strength = -1; while (!q.empty()) { auto [node, strength] = q.front(); q.pop(); if (strength > routers[node]) continue; if (node == n - 1) { max_strength = max(max_strength, strength); } for (auto [next, weight] : graph[node]) { if (strength > LLONG_MAX / weight) continue; ll new_strength = strength * weight; if (new_strength <= routers[next]) { q.emplace(next, new_strength); } } } return max_strength; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int T; scanf("%d", &T); while (T--) { int n, m; scanf("%d %d", &n, &m); vector<ll> routers(n); for (int i = 0; i < n; i++) { scanf("%lld", &routers[i]); } vector<vector<pair<int, ll>>> graph(n); for (int i = 0; i < m; i++) { int a, b; ll w; scanf("%d %d %lld", &a, &b, &w); --a, --b; graph[a].emplace_back(b, w); } ll max_strength = bfs(n, routers, graph); printf("%lld\n", max_strength); } return 0; } |