#include <bits/stdc++.h> using namespace std; void test_case() { int n, m; cin >> n >> m; vector<int> limit(n); for (int i = 0; i < n; i++) { cin >> limit[i]; } vector<vector<pair<int,int>>> edges(n); auto inv = edges; for (int i = 0; i < m; i++) { int a, b, mul; cin >> a >> b >> mul; a--; b--; edges[a].emplace_back(b, mul); inv[b].emplace_back(a, mul); } int MAX = *max_element(limit.begin(), limit.end()); int L1 = 3 * sqrt(MAX + 0.5); // 10^5 int L2 = MAX / L1 + 2; // 10^4 vector<vector<bool>> yes(L1 + 1, vector<bool>(n)); yes[1][0] = true; for (int d = 1; d <= L1; d++) { vector<int> waiting; for (int a = 0; a < n; a++) { if (yes[d][a]) { for (auto [b, mul] : edges[a]) { if ((long long) d * mul <= min(L1,limit[b]) && !yes[d*mul][b]) { yes[d*mul][b] = true; if (mul == 1 && b < a) { waiting.push_back(b); } } } } } for (int i = 0; i < (int) waiting.size(); i++) { int a = waiting[i]; assert(yes[d][a]); for (auto [b, mul] : edges[a]) { if ((long long) d * mul <= min(L1,limit[b]) && !yes[d*mul][b]) { yes[d*mul][b] = true; if (mul == 1) { waiting.push_back(b); } } } } } int answer = -1; for (int d = 1; d <= L1; d++) { if (yes[d][n-1]) { answer = d; } } vector<vector<int>> upTo(L1 + 1, vector<int>(n)); for (int d = 1; d <= L1; d++) { upTo[d] = upTo[d-1]; for (int a = 0; a < n; a++) { if (yes[d][a]) { upTo[d][a] = d; } } } vector<vector<int>> dp(L2 + 1, vector<int>(n)); dp[1][n-1] = limit[n-1]; for (int d = 1; d <= L2; d++) { set<pair<int,int>, greater<pair<int,int>>> s; for (int a = 0; a < n; a++) { if (dp[d][a]) { s.insert({dp[d][a], a}); } } while (!s.empty()) { auto [me,a] = *s.begin(); assert((long long) me * d <= limit[n-1]); s.erase(s.begin()); if (dp[d][a] != me) { continue; } for (auto [b,mul] : inv[a]) { int big = upTo[min(L1,me/mul)][b]; if (big) { answer = max(answer, big * mul * d); } if ((long long) d * mul <= L2) { int maybe = min(me / mul, limit[b]); if (maybe > dp[d*mul][b]) { dp[d*mul][b] = maybe; if (mul == 1) { s.insert({maybe, b}); } } } } } } cout << answer << "\n"; } int main() { int T; cin >> T; while (T--) { test_case(); } }
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 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 | #include <bits/stdc++.h> using namespace std; void test_case() { int n, m; cin >> n >> m; vector<int> limit(n); for (int i = 0; i < n; i++) { cin >> limit[i]; } vector<vector<pair<int,int>>> edges(n); auto inv = edges; for (int i = 0; i < m; i++) { int a, b, mul; cin >> a >> b >> mul; a--; b--; edges[a].emplace_back(b, mul); inv[b].emplace_back(a, mul); } int MAX = *max_element(limit.begin(), limit.end()); int L1 = 3 * sqrt(MAX + 0.5); // 10^5 int L2 = MAX / L1 + 2; // 10^4 vector<vector<bool>> yes(L1 + 1, vector<bool>(n)); yes[1][0] = true; for (int d = 1; d <= L1; d++) { vector<int> waiting; for (int a = 0; a < n; a++) { if (yes[d][a]) { for (auto [b, mul] : edges[a]) { if ((long long) d * mul <= min(L1,limit[b]) && !yes[d*mul][b]) { yes[d*mul][b] = true; if (mul == 1 && b < a) { waiting.push_back(b); } } } } } for (int i = 0; i < (int) waiting.size(); i++) { int a = waiting[i]; assert(yes[d][a]); for (auto [b, mul] : edges[a]) { if ((long long) d * mul <= min(L1,limit[b]) && !yes[d*mul][b]) { yes[d*mul][b] = true; if (mul == 1) { waiting.push_back(b); } } } } } int answer = -1; for (int d = 1; d <= L1; d++) { if (yes[d][n-1]) { answer = d; } } vector<vector<int>> upTo(L1 + 1, vector<int>(n)); for (int d = 1; d <= L1; d++) { upTo[d] = upTo[d-1]; for (int a = 0; a < n; a++) { if (yes[d][a]) { upTo[d][a] = d; } } } vector<vector<int>> dp(L2 + 1, vector<int>(n)); dp[1][n-1] = limit[n-1]; for (int d = 1; d <= L2; d++) { set<pair<int,int>, greater<pair<int,int>>> s; for (int a = 0; a < n; a++) { if (dp[d][a]) { s.insert({dp[d][a], a}); } } while (!s.empty()) { auto [me,a] = *s.begin(); assert((long long) me * d <= limit[n-1]); s.erase(s.begin()); if (dp[d][a] != me) { continue; } for (auto [b,mul] : inv[a]) { int big = upTo[min(L1,me/mul)][b]; if (big) { answer = max(answer, big * mul * d); } if ((long long) d * mul <= L2) { int maybe = min(me / mul, limit[b]); if (maybe > dp[d*mul][b]) { dp[d*mul][b] = maybe; if (mul == 1) { s.insert({maybe, b}); } } } } } } cout << answer << "\n"; } int main() { int T; cin >> T; while (T--) { test_case(); } } |