#include <cstdio> #include <vector> #include <algorithm> using namespace std; #define MAX 201 typedef long long ll; struct EE { int b; ll w; bool operator==(const EE& other) const { return w == other.w && b == other.b; } bool operator<(const EE& other) const { return w == other.w? b < other.b : w > other.w; } }; namespace std { template <> struct hash<EE> { size_t operator()(const EE& s) const { return hash<ll>()(s.w*100+s.b); } }; } vector<EE> E[MAX]; ll p[MAX], result; int T,n,m,a; int vid[MAX]; #define MAP_SIZE 100000037 //#define MAP_SIZE 1000037 #define HASH2 8191 //ll myhash[100][MAP_SIZE]; ll myhash[MAP_SIZE+64]; static bool visited(ll x, int id) { ll v = vid[id%MAX]; ll h = (x*50021+v*1000037) % 6400002319; //% 100000037*64; //if(h&15) return false; h/=16; ll s = myhash[h/64]; int visited = s & (1<<(h&63)); myhash[h/64] |= (1<<(h&63)); return visited; /* int h2 = (x%HASH2)+1; ll s = myhash[h]; if(s==0) { myhash[h] = (h2<<1) | (v&1) | (1<<((v/2)+14)); return false; } else { if ((v&1) == (s&1) && ((s>>1)&0x1fff) == h2) { ll visited = (s & (1<<((v/2)+14))); myhash[h] |= (1<<((v/2)+14)); return visited; } }*/ return false; } void clear_visited() { // for(int i=0;i<MAP_SIZE;i++) myhash[i] = 0; } #define D(x) void dfs(int x, int v, int depth=0) { int i; if(depth > 3100) return; for(i=0;i<E[v].size();i++) { ll nx = x*E[v][i].w; int nv = E[v][i].b; D(printf("ns: %d w:%lld p:%lld--\n",ns.b, ns.w, p[ns.b]);) if (nx <= p[nv] && (!visited(nx, nv))) { D(printf("%d %lld --\n",ns.b, ns.w )); if (nv == n) result = max(result, nx); dfs(nx,nv, depth+1); } } } int ids[] = {95, 96, 38, 43, 12, 67, 92, 3, 14, 29, 9, 4, 42, 63, 22, 34, 56, 84, 90, 65, 25, 83, 57, 69, 41, 60, 24, 18, 21, 28, 80, 88, 81, 98, 89, 36, 70, 30, 100, 97, 74, 48, 62, 77, 64, 23, 53, 6, 50, 10, 40, 1, 72, 15, 82, 76, 11, 13, 58, 17, 73, 39, 78, 31, 93, 45, 99, 2, 46, 61, 16, 19, 79, 35, 51, 26, 59, 91, 47, 87, 55, 85, 27, 52, 20, 54, 8, 7, 32, 33, 71, 68, 37, 5, 86, 94, 49, 44, 66, 75}; int ids_count=1; int main() { scanf("%d", &T); while(T--) { scanf("%d %d", &n,&m); for(int i=0;i<MAX;i++) E[i].clear(); for(int i=1;i<=n;i++){ scanf("%lld", &p[i]); vid[i] = ids_count++; } for(int i=0;i<m;i++) { EE e; scanf("%d %d %lld", &a, &e.b, &e.w); if (a == e.b && e.w == 1) continue; E[a].push_back(e); } for(int i=1;i<=n;i++) { std::sort(E[i].begin(), E[i].end()); auto last = std::unique(E[i].begin(), E[i].end()); E[i].erase(last, E[i].end()); } result = -1; if (n == 1) result =1; clear_visited(); dfs(1, 1); // fprintf(stderr, "hash size %d col: %d\n", data_size, h_col); printf("%lld\n", result); } }
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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; #define MAX 201 typedef long long ll; struct EE { int b; ll w; bool operator==(const EE& other) const { return w == other.w && b == other.b; } bool operator<(const EE& other) const { return w == other.w? b < other.b : w > other.w; } }; namespace std { template <> struct hash<EE> { size_t operator()(const EE& s) const { return hash<ll>()(s.w*100+s.b); } }; } vector<EE> E[MAX]; ll p[MAX], result; int T,n,m,a; int vid[MAX]; #define MAP_SIZE 100000037 //#define MAP_SIZE 1000037 #define HASH2 8191 //ll myhash[100][MAP_SIZE]; ll myhash[MAP_SIZE+64]; static bool visited(ll x, int id) { ll v = vid[id%MAX]; ll h = (x*50021+v*1000037) % 6400002319; //% 100000037*64; //if(h&15) return false; h/=16; ll s = myhash[h/64]; int visited = s & (1<<(h&63)); myhash[h/64] |= (1<<(h&63)); return visited; /* int h2 = (x%HASH2)+1; ll s = myhash[h]; if(s==0) { myhash[h] = (h2<<1) | (v&1) | (1<<((v/2)+14)); return false; } else { if ((v&1) == (s&1) && ((s>>1)&0x1fff) == h2) { ll visited = (s & (1<<((v/2)+14))); myhash[h] |= (1<<((v/2)+14)); return visited; } }*/ return false; } void clear_visited() { // for(int i=0;i<MAP_SIZE;i++) myhash[i] = 0; } #define D(x) void dfs(int x, int v, int depth=0) { int i; if(depth > 3100) return; for(i=0;i<E[v].size();i++) { ll nx = x*E[v][i].w; int nv = E[v][i].b; D(printf("ns: %d w:%lld p:%lld--\n",ns.b, ns.w, p[ns.b]);) if (nx <= p[nv] && (!visited(nx, nv))) { D(printf("%d %lld --\n",ns.b, ns.w )); if (nv == n) result = max(result, nx); dfs(nx,nv, depth+1); } } } int ids[] = {95, 96, 38, 43, 12, 67, 92, 3, 14, 29, 9, 4, 42, 63, 22, 34, 56, 84, 90, 65, 25, 83, 57, 69, 41, 60, 24, 18, 21, 28, 80, 88, 81, 98, 89, 36, 70, 30, 100, 97, 74, 48, 62, 77, 64, 23, 53, 6, 50, 10, 40, 1, 72, 15, 82, 76, 11, 13, 58, 17, 73, 39, 78, 31, 93, 45, 99, 2, 46, 61, 16, 19, 79, 35, 51, 26, 59, 91, 47, 87, 55, 85, 27, 52, 20, 54, 8, 7, 32, 33, 71, 68, 37, 5, 86, 94, 49, 44, 66, 75}; int ids_count=1; int main() { scanf("%d", &T); while(T--) { scanf("%d %d", &n,&m); for(int i=0;i<MAX;i++) E[i].clear(); for(int i=1;i<=n;i++){ scanf("%lld", &p[i]); vid[i] = ids_count++; } for(int i=0;i<m;i++) { EE e; scanf("%d %d %lld", &a, &e.b, &e.w); if (a == e.b && e.w == 1) continue; E[a].push_back(e); } for(int i=1;i<=n;i++) { std::sort(E[i].begin(), E[i].end()); auto last = std::unique(E[i].begin(), E[i].end()); E[i].erase(last, E[i].end()); } result = -1; if (n == 1) result =1; clear_visited(); dfs(1, 1); // fprintf(stderr, "hash size %d col: %d\n", data_size, h_col); printf("%lld\n", result); } } |