#include #include #include #include #include using namespace std; int main(){ freopen( "fart.in", "r", stdin ); freopen( "fart.out", "w", stdout ); ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, K; cin >> N >> M >> K; // Прочитаме кои маски се продават във всеки град (като битова маска) vector cityMasks(N, 0); for (int i = 0; i < N; i++){ string s; cin >> s; int mask = 0; for (int j = 0; j < K; j++){ if (s[j] == '1'){ mask |= (1 << j); } } cityMasks[i] = mask; } // Построяване на графа – всеки път има газова битова маска vector>> graph(N); for (int i = 0; i < M; i++){ int a, b; string gas; cin >> a >> b >> gas; a--; b--; int gasMask = 0; for (int j = 0; j < K; j++){ if (gas[j] == '1'){ gasMask |= (1 << j); } } graph[a].push_back({b, gasMask}); graph[b].push_back({a, gasMask}); } // Ще използваме 0-1 BFS върху състояния: (град, maskState) // Разстоянието ще е броят на закупените маски const int INF = numeric_limits::max(); vector> dist(N, vector(1 << K, INF)); // Начално състояние: град 0 (т.е. 1 според условието), без закупени маски. deque> dq; dist[0][0] = 0; dq.push_back({0, 0}); while(!dq.empty()){ auto [u, mset] = dq.front(); dq.pop_front(); int cost = dist[u][mset]; // Ако сме достигнали град N, извеждаме минималната цена. if(u == N - 1){ cout << cost << "\n"; return 0; } // 1. Покупка на маска (ако градът продава дадена и я нямаме) int available = cityMasks[u]; for (int i = 0; i < K; i++){ // Ако градът продава маска за газ i и я нямаме още if ((available & (1 << i)) && ((mset & (1 << i)) == 0)){ int newMaskState = mset | (1 << i); if (dist[u][newMaskState] > cost + 1){ dist[u][newMaskState] = cost + 1; dq.push_back({u, newMaskState}); // покачване на цената с 1 } } } // 2. Преминаване по път (ако с наличните маски покриваме изискванията за газове) for (auto &edge : graph[u]){ int v = edge.first; int req = edge.second; // Ако разполагаме с всички необходими маски за този път if ((mset & req) == req){ if (dist[v][mset] > cost){ dist[v][mset] = cost; dq.push_front({v, mset}); // преминаване без допълнителна цена } } } } // Ако не можем да достигнем град N, извеждаме -1 (но според условието винаги има път) cout << -1 << "\n"; return 0; }