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
// clang-format off
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(auto i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<"("<<p.first<<", "<<p.second<<")";}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<"}";}
#ifdef DEBUG
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<"\n";}(X)
#else
#define debug(...) {}
#endif
// clang-format on

struct MonoSet
{
    // (band, mul) with increasing band, mul decreases
    set<pair<int, int>> data;
    bool insert(int band, int mul);
    int best_deal(int input);
};

mt19937 rng(2387619234);

int nverts, nedges;
vector<int> vbands;
vector<MonoSet> proposals;
vector<vector<pair<int, int>>> radj;
vector<vector<int>> radj1;  // for edges of weight 1

void input();
void try_with_me(int v, int band, int mul);

int
main()
{
    cin.tie(0)->sync_with_stdio(0);
    int ntests;
    cin >> ntests;
    while (ntests--) {
        input();
        proposals.clear();
        proposals.resize(nverts + 1);
        try_with_me(nverts, vbands[nverts], 1);
        cout << proposals[1].best_deal(1) << "\n";
    }
    return 0;
}

void
try_with_me(int v, int band, int mul)
{
    // Ensure this path improves anything
    if (proposals[v].insert(band, mul) == false) return;
    debug(v, band, mul);

    // See from which verts we might get here
    for (const auto& from : radj[v]) {
        // Assure we can withstand this connection
        if (from.second > band) continue;

        // Recurse with new bandwith and mul factor
        try_with_me(from.first,
                    min(vbands[from.first], band / from.second),
                    mul * from.second);
    }

    // The same but for edges with factor 1
    for (const auto& from : radj1[v]) {
        // Assure we can withstand this connection
        if (1 > band) continue;  // is it needed?
        try_with_me(from, min(vbands[from], band), mul);
    }
}

void
input()
{
    cin >> nverts >> nedges;
    vbands.resize(nverts + 1);
    FOR (v, 1, nverts) cin >> vbands[v];
    radj.clear();
    radj.resize(nverts + 1);
    radj1.clear();
    radj1.resize(nverts + 1);
    REP (e, nedges) {
        int a, b, mul;
        cin >> a >> b >> mul;
        if (mul == 1)
            radj1[b].emplace_back(a);
        else
            radj[b].emplace_back(a, mul);
    }

    // Randomly permute adjacency lists so that this solve is unbeatable
    FOR (v, 1, nverts) shuffle(radj[v].begin(), radj[v].end(), rng);
}

bool
MonoSet::insert(int band, int mul)
{
    // Check whether it's worth inserting it
    auto it = data.lower_bound({band, 0});
    if (it != data.end() && mul <= it->second) return false;

    // Insert it
    it = data.insert({band, mul}).first;

    // Delete all previous with second <= mul
    while (it != data.begin() && prev(it)->second <= mul) data.erase(prev(it));
    return true;
}

int
MonoSet::best_deal(int input)
{
    auto it = data.lower_bound({input, 0});
    if (it == data.end()) return -1;
    return input * it->second;
}