#include #define endl '\n' const int MAXN = 11; const int MAXK = (1 << 15); const int INF = 100; std::vector < std::pair < int, std::bitset < 15 > > > adj[MAXN]; int n, m, k; std::bitset < 15 > g[MAXN]; int d[MAXN]; std::unordered_set < int > used[MAXN]; std::vector < std::bitset < 15 > > allm[MAXN]; int cost(std::bitset < 15 > v) { return v.count(); } struct state { int u; std::bitset < 15 > masks; int c; state(){}; state(int _u, std::bitset < 15 > _masks) { u = _u; masks = _masks; c = cost(masks); } friend bool operator<(state st1, state st2) { return st1.c > st2.c; } }; void read() { std::cin >> n >> m >> k; for(int i = 0; i < n; i++) { std::cin >> g[i]; } std::bitset < 15 > vc; for(int i = 0; i < m; i++) { int u, v; std::cin >> u >> v; u--; v--; std::cin >> vc; adj[u].push_back({v, vc}); adj[v].push_back({u, vc}); } } void gen(int &u, int pos, std::bitset < 15 > &v) { if(pos == k) { allm[u].push_back(v); return; } gen(u, pos + 1, v); if(g[u][pos] == 1) { v.set(pos); gen(u, pos + 1, v); v.reset(pos); } } void genall() { for(int i = 0; i < n; i++) { std::bitset < 15 > vx; gen(i, 0, vx); } } void solve() { for(int i = 0; i < n; i++) { d[i] = INF; } std::priority_queue < state > pq; for(std::bitset < 15 > &mask : allm[0]) { pq.push(state(0, mask)); } while(!pq.empty()) { state st = pq.top(); pq.pop(); int u = st.u; std::bitset < 15 > masks = st.masks; int curcost = st.c; //cout << "Node : " << u << endl; //cout << "Masks : " << masks << endl; //cout << "Curcost : " << curcost << endl; //cout << endl; d[u] = std::min(curcost, d[u]); if(u == n - 1) { std::cout << d[u] << endl; return; } int intmask = (int)masks.to_ulong(); if(used[u].count(intmask)) continue; used[u].insert(intmask); for(std::pair < int, std::bitset < 15 > > &e : adj[u]) { //cout << "Edge to : " << v << endl; //cout << "Needs : " << need << endl; if((masks & e.second) != e.second) continue; for(std::bitset < 15 > &newmask : allm[e.first]) { std::bitset < 15 > cur = masks | newmask; pq.push(state(e.first, cur)); } } } std::cout << d[n - 1] << endl; } int main() { #ifdef ONLINE_JUDGE freopen("fart.in", "r", stdin); freopen("fart.out", "w", stdout); #endif std::ios_base :: sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); read(); genall(); solve(); return 0; }