#pragma GCC optimize("O3") #include #define endl '\n' using namespace std; const int MAXN = 20; const int INF = 1e9; class Graph { private: struct Edge { int to; vector needMasks; Edge(){} Edge(int to, vector neededMasks) { this->to = to; this->needMasks = neededMasks; } }; int N, K; vector graph[MAXN]; vector availableMasksPerTown[MAXN]; bool used[MAXN]; bool buyedMasks[MAXN]; int Generate(int pos, bool *allowedMasks) { if (pos == K) { int cnt = 0; for (int i = 0; i < K; i++) { cnt += allowedMasks[i]; //cout << allowedMasks[i]; } //cout << endl; return (Check(allowedMasks)?cnt:INF); } int ans = INF; allowedMasks[pos] = true; ans = min(ans, Generate(pos+1, allowedMasks)); allowedMasks[pos] = false; ans = min(ans, Generate(pos+1, allowedMasks)); return ans; } public: Graph(){} Graph(int N, int K) :N(N), K(K){} void AddTownInfo(int town, string& input) { for (int i = 0; i < (int)input.size(); i++) { if (input[i] == '0') continue; availableMasksPerTown[town].push_back(i); } } void AddEdge(int u, int v, string& input) { vector neededMasks; for (int i = 0; i < (int)input.size(); i++) { if (input[i] == '0') continue; neededMasks.push_back(i); } graph[u].emplace_back(v, neededMasks); graph[v].emplace_back(u, neededMasks); } bool Check(const bool *allowedMasks) { memset(used, false, sizeof(used)); memset(buyedMasks, false, sizeof(buyedMasks)); queue q; q.push(1); used[1] = true; for (int availableMask: availableMasksPerTown[1]) { if (allowedMasks[availableMask] == true) { buyedMasks[availableMask] = true; } } while (!q.empty()) { int node = q.front(); q.pop(); for (const Edge& edge: graph[node]) { if (used[edge.to]) continue; bool canEnter = true; for (int neededMask:edge.needMasks) { if (buyedMasks[neededMask] == false) { canEnter = false; break; } } if (canEnter == false) continue; for (int availableMask: availableMasksPerTown[edge.to]) { if (allowedMasks[availableMask] == true) { buyedMasks[availableMask] = true; } } used[edge.to] = true; q.push(edge.to); } } return used[N]; } int Solve() { bool allowedMasks[MAXN]; memset(allowedMasks, false, sizeof(allowedMasks)); return this->Generate(0, allowedMasks); } }; int main() { #ifndef __LOCAL__ freopen("fart.in", "r", stdin); freopen("fart.out", "w", stdout); #endif // __LOCAL__ int N, M, K; cin >> N >> M >> K; Graph *graph = new Graph(N, K); for (int i = 1; i <= N; i++) { string s; cin >> s; graph->AddTownInfo(i, s); } for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; string s; cin >> s; graph->AddEdge(u, v, s); } cout << graph->Solve() << endl; delete graph; return 0; }