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
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <queue>
#include <tuple>

int t,n,m,a,b;
long long p,w;
//res startval poz

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(NULL);
    std::cin>>t;
    //TODO cykle z krawedzi 1;
    for(int test=0;test<t;test++){
        std::priority_queue<std::tuple<long long,long long,int>> kol;
        std::vector<long long> city_cap;
        std::cin>>n>>m;
        
        std::vector<std::pair<long long,long long> >sma_in_cit;
        std::vector<std::vector<std::pair<int,long long> > > edges(n);
        for(int i=0;i<n;i++){
            std::cin>>p;
            city_cap.emplace_back(p);
            sma_in_cit.emplace_back(10000000000,10000000000);
        }
        for(int i=0;i<m;i++){
            std::cin>>a>>b>>w;
            a--;b--;
            edges[b].emplace_back(a,w);
        }
    
        kol.emplace(city_cap[n-1],city_cap[n-1],n-1);
        long long best_res=-1;
        while(!kol.empty()){
            //std::cout<<kol.size()<<"\n";
            //const auto [res,stval,poz]=kol.top();
            std::tuple<long long, long long, int> temp = kol.top();
            long long res = std::get<0>(temp);
            long long stval = std::get<1>(temp);
            int poz = std::get<2>(temp);
            
            kol.pop();
            std::pair<long long,long long> x=std::make_pair(res,stval);
            if(sma_in_cit[poz]<=x)
                continue;
            else
                sma_in_cit[poz]=x;
                
            //if(test==6858)
            //        std::cerr<<res<<" "<<stval<<" "<<poz<<std::endl;
            if(poz==0){
                if(res/stval>best_res)
                    best_res=res/stval;
                if(stval==1){
                    break;
                }
            }
            
            for(const auto& [mias, mnoz] :edges[poz]){
                auto st=std::min(city_cap[mias],stval/mnoz);
                auto re=(res/stval)*st*mnoz;
                //if(test==6858)
                //    std::cerr<<"xx "<<re<<" "<<st<<" "<<mias<<"\n";
                if(re>0)
                    kol.emplace(re,st,mias);
            }
            
            //std::cout<<kol.size()<<"\n";
        }
    std::cout<<best_res<<std::endl;
    }
}