#include #include #include #include #include #include using namespace std; const int MAX_K = 20; struct State { int city; int mask; int mask_count; }; int main() { ifstream fin("fart.in"); ofstream fout("fart.out"); int N, M, K; fin >> N >> M >> K; vector city_masks(N); for (int i = 0; i < N; ++i) { string mask_str; fin >> mask_str; int mask = 0; for (int j = 0; j < K; ++j) { if (mask_str[j] == '1') { mask |= (1 << j); } } city_masks[i] = mask; } vector>> adj(N); for (int i = 0; i < M; ++i) { int a, b; string gas_str; fin >> a >> b >> gas_str; a--; b--; int gas_mask = 0; for (int j = 0; j < K; ++j) { if (gas_str[j] == '1') { gas_mask |= (1 << j); } } adj[a].emplace_back(b, gas_mask); adj[b].emplace_back(a, gas_mask); } queue q; q.push({0, city_masks[0], __builtin_popcount(city_masks[0])}); vector> visited(N); visited[0].insert(city_masks[0]); int min_masks = K + 1; while (!q.empty()) { State current = q.front(); q.pop(); if (current.city == N - 1) { min_masks = min(min_masks, current.mask_count); continue; } for (auto& edge : adj[current.city]) { int next_city = edge.first; int gas_mask = edge.second; int required_mask = gas_mask & ~current.mask; if (required_mask == 0) { int new_mask = current.mask; if (visited[next_city].find(new_mask) == visited[next_city].end()) { visited[next_city].insert(new_mask); q.push({next_city, new_mask, current.mask_count}); } } else { int new_mask = current.mask | city_masks[current.city]; int new_mask_count = current.mask_count + __builtin_popcount(city_masks[current.city] & required_mask); if (visited[next_city].find(new_mask) == visited[next_city].end()) { visited[next_city].insert(new_mask); q.push({next_city, new_mask, new_mask_count}); } } } } fout << min_masks << endl; fin.close(); fout.close(); return 0; }