#include <cstdio> #include <queue> #include <set> #include <utility> #include <vector> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define VAR(v,w) __typeof(w) v=(w) #define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it) #define PB push_back #define MP make_pair #define FT first #define SD second #define INT(x) int x; scanf("%d", &x) typedef long long LL; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<VI> VVI; int p[100], e[200], w[200]; set<int> r[100]; VVI g; void test() { INT(n); INT(m); REP(i,n) scanf("%d", &p[i]); g.clear(); g.resize(n); REP(j,m) { INT(a); INT(b); INT(ww); --a; --b; g[a].PB(j); e[j] = b; w[j] = ww; } REP(i,n) r[i].clear(); queue<PII> q; r[0].insert(1); q.push(MP(0, 1)); while (!q.empty()) { int v = q.front().FT, rr = q.front().SD; q.pop(); FORE(it,g[v]) { int v2 = e[*it], ww = w[*it]; LL rr2 = LL(rr) * ww; if (rr2 > p[v2]) continue; int rr2i = rr2; if (r[v2].find(rr2i) == r[v2].end()) { r[v2].insert(rr2i); q.push(MP(v2, rr2i)); } } } if (r[n - 1].empty()) { printf("-1\n"); return; } VAR(it,r[n - 1].end()); --it; printf("%d\n", *it); } int main() { INT(t); REP(tt,t) test(); }
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 <cstdio> #include <queue> #include <set> #include <utility> #include <vector> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define VAR(v,w) __typeof(w) v=(w) #define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it) #define PB push_back #define MP make_pair #define FT first #define SD second #define INT(x) int x; scanf("%d", &x) typedef long long LL; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<VI> VVI; int p[100], e[200], w[200]; set<int> r[100]; VVI g; void test() { INT(n); INT(m); REP(i,n) scanf("%d", &p[i]); g.clear(); g.resize(n); REP(j,m) { INT(a); INT(b); INT(ww); --a; --b; g[a].PB(j); e[j] = b; w[j] = ww; } REP(i,n) r[i].clear(); queue<PII> q; r[0].insert(1); q.push(MP(0, 1)); while (!q.empty()) { int v = q.front().FT, rr = q.front().SD; q.pop(); FORE(it,g[v]) { int v2 = e[*it], ww = w[*it]; LL rr2 = LL(rr) * ww; if (rr2 > p[v2]) continue; int rr2i = rr2; if (r[v2].find(rr2i) == r[v2].end()) { r[v2].insert(rr2i); q.push(MP(v2, rr2i)); } } } if (r[n - 1].empty()) { printf("-1\n"); return; } VAR(it,r[n - 1].end()); --it; printf("%d\n", *it); } int main() { INT(t); REP(tt,t) test(); } |