#include "bits/stdc++.h" using namespace std; using ll = long long; const ll INF = 1e9 + 7; ll ans; int n, m; int used[105]; int idx_self[105]; set <array<ll, 2>> st[105]; void dfs(vector <vector <pair <ll, ll>>> &g, vector <vector <ll>> &loops, vector <ll> &p, vector <bool> &flag, vector <ll> &dist, vector <ll> &neck, ll v, ll cur) { if (st[v].count({cur, idx_self[v]})) return; else st[v].insert({cur, idx_self[v]}); if (v == n) { ans = max(ans, cur); } if (neck[v] < cur || cur * dist[v] > p[n]) return; if (!used[v]) { if (idx_self[v] < loops[v].size() && cur * loops[v][idx_self[v]] <= p[v]) dfs(g, loops, p, flag, dist, neck, v, cur * loops[v][idx_self[v]]); if (idx_self[v] + 1 < loops[v].size()) { idx_self[v]++; dfs(g, loops, p, flag, dist, neck, v, cur); idx_self[v]--; } } used[v]++; for (int i = 0; i < g[v].size(); i++) { auto [e, w] = g[v][i]; if (!flag[e]) continue; if (cur * w <= p[e]) { dfs(g, loops, p, flag, dist, neck, e, cur * w); } } used[v]--; } void solve() { cin >> n >> m; vector <ll> p(n + 1, 0); for (int i = 1; i <= n; i++) cin >> p[i]; vector <vector <pair <ll, ll>>> g(n + 1), gr(n + 1); set <array<ll, 3>> edges; for (int i = 0; i < m; i++) { int a, b, w; cin >> a >> b >> w; if (!(a == b && w == 1)) edges.insert({a, b, w}); g[a].push_back({b, w}); gr[b].push_back({a, w}); } vector <bool> flag(n + 1, false); queue <int> q; flag[n] = true; q.push(n); while (!q.empty()) { int cur = q.front(); q.pop(); for (auto [e, w] : gr[cur]) { if (!flag[e]) { flag[e] = true; q.push(e); } } } if (!flag[1]) { cout << -1 << '\n'; return; } vector <ll> dist(n + 1, INF); priority_queue <pair <ll, int>, vector <pair <ll, int>>, greater<pair <ll, int>>> pq; dist[1] = 1; pq.push({1, 1}); while (!pq.empty()) { ll t = pq.top().first, cur = pq.top().second; pq.pop(); if (t != dist[cur]) continue; for (auto [e, w] : g[cur]) { if (flag[e]) if (t * w < dist[e] && t * w <= p[e]) { dist[e] = t * w; pq.push({t * w, e}); } } } if (dist[n] == INF) { cout << -1 << '\n'; return; } ans = dist[n]; for (int i = 1; i <= n; i++) dist[i] = INF; dist[n] = 1; pq.push({1, n}); while (!pq.empty()) { ll t = pq.top().first, cur = pq.top().second; pq.pop(); if (t != dist[cur]) continue; for (auto [e, w] : gr[cur]) if (flag[e]) { if (t * w < dist[e]) { dist[e] = t * w; pq.push({t * w, e}); } } } vector <ll> neck(n + 1, 0); neck[n] = INF; priority_queue <pair <ll, int>> pq2; pq2.push({INF, n}); while (!pq2.empty()) { ll val = pq2.top().first, cur = pq2.top().second; pq2.pop(); if (val != neck[cur]) continue; for (auto [e, w] : gr[cur]) if (flag[e]) { if (min(val, p[e]) > neck[e]) { neck[e] = min(val, p[e]); pq2.push({neck[e], e}); } } } vector <vector <ll>> loops(n + 1); for (int i = 1; i <= n; i++) g[i].clear(); for (auto [a, b, w] : edges) { if (a == b) loops[a].push_back(w); else g[a].push_back({b, w}); } for (int i = 1; i <= n; i++) { used[i] = 0; idx_self[i] = 0; st[i].clear(); } dfs(g, loops, p, flag, dist, neck, 1, 1); cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.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 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 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 | #include "bits/stdc++.h" using namespace std; using ll = long long; const ll INF = 1e9 + 7; ll ans; int n, m; int used[105]; int idx_self[105]; set <array<ll, 2>> st[105]; void dfs(vector <vector <pair <ll, ll>>> &g, vector <vector <ll>> &loops, vector <ll> &p, vector <bool> &flag, vector <ll> &dist, vector <ll> &neck, ll v, ll cur) { if (st[v].count({cur, idx_self[v]})) return; else st[v].insert({cur, idx_self[v]}); if (v == n) { ans = max(ans, cur); } if (neck[v] < cur || cur * dist[v] > p[n]) return; if (!used[v]) { if (idx_self[v] < loops[v].size() && cur * loops[v][idx_self[v]] <= p[v]) dfs(g, loops, p, flag, dist, neck, v, cur * loops[v][idx_self[v]]); if (idx_self[v] + 1 < loops[v].size()) { idx_self[v]++; dfs(g, loops, p, flag, dist, neck, v, cur); idx_self[v]--; } } used[v]++; for (int i = 0; i < g[v].size(); i++) { auto [e, w] = g[v][i]; if (!flag[e]) continue; if (cur * w <= p[e]) { dfs(g, loops, p, flag, dist, neck, e, cur * w); } } used[v]--; } void solve() { cin >> n >> m; vector <ll> p(n + 1, 0); for (int i = 1; i <= n; i++) cin >> p[i]; vector <vector <pair <ll, ll>>> g(n + 1), gr(n + 1); set <array<ll, 3>> edges; for (int i = 0; i < m; i++) { int a, b, w; cin >> a >> b >> w; if (!(a == b && w == 1)) edges.insert({a, b, w}); g[a].push_back({b, w}); gr[b].push_back({a, w}); } vector <bool> flag(n + 1, false); queue <int> q; flag[n] = true; q.push(n); while (!q.empty()) { int cur = q.front(); q.pop(); for (auto [e, w] : gr[cur]) { if (!flag[e]) { flag[e] = true; q.push(e); } } } if (!flag[1]) { cout << -1 << '\n'; return; } vector <ll> dist(n + 1, INF); priority_queue <pair <ll, int>, vector <pair <ll, int>>, greater<pair <ll, int>>> pq; dist[1] = 1; pq.push({1, 1}); while (!pq.empty()) { ll t = pq.top().first, cur = pq.top().second; pq.pop(); if (t != dist[cur]) continue; for (auto [e, w] : g[cur]) { if (flag[e]) if (t * w < dist[e] && t * w <= p[e]) { dist[e] = t * w; pq.push({t * w, e}); } } } if (dist[n] == INF) { cout << -1 << '\n'; return; } ans = dist[n]; for (int i = 1; i <= n; i++) dist[i] = INF; dist[n] = 1; pq.push({1, n}); while (!pq.empty()) { ll t = pq.top().first, cur = pq.top().second; pq.pop(); if (t != dist[cur]) continue; for (auto [e, w] : gr[cur]) if (flag[e]) { if (t * w < dist[e]) { dist[e] = t * w; pq.push({t * w, e}); } } } vector <ll> neck(n + 1, 0); neck[n] = INF; priority_queue <pair <ll, int>> pq2; pq2.push({INF, n}); while (!pq2.empty()) { ll val = pq2.top().first, cur = pq2.top().second; pq2.pop(); if (val != neck[cur]) continue; for (auto [e, w] : gr[cur]) if (flag[e]) { if (min(val, p[e]) > neck[e]) { neck[e] = min(val, p[e]); pq2.push({neck[e], e}); } } } vector <vector <ll>> loops(n + 1); for (int i = 1; i <= n; i++) g[i].clear(); for (auto [a, b, w] : edges) { if (a == b) loops[a].push_back(w); else g[a].push_back({b, w}); } for (int i = 1; i <= n; i++) { used[i] = 0; idx_self[i] = 0; st[i].clear(); } dfs(g, loops, p, flag, dist, neck, 1, 1); cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) solve(); } |