P7297 [USACO21JAN] Telephone G

Farmer John has $N$ cows, numbered $1 \ldots N$, standing in a line ($1 \le N \le 5 \cdot 10^4$). The breed ID of cow $i$ is $b_i$, in the range $1 \ldots K$, where $1 \le K \le 50$. The cows need your help to find the best way to transmit a message from cow $1$ to cow $N$. Transmitting a message from cow $i$ to cow $j$ takes time $|i-j|$. However, not all breeds of cows are willing to talk to each other, as described by a $K \times K$ matrix $S$. If a cow of breed $i$ is willing to transmit a message to a cow of breed $j$, then $S_{ij}=1$, otherwise it is $0$. It is not guaranteed that $S_{ij}=S_{ji}$, and it is possible that $S_{ii}=0$ if cows of breed $i$ are not willing to communicate with each other. Find the minimum time required to transmit the message.

The first line contains $N$ and $K$. The next line contains $N$ space-separated integers $b_1,b_2,\dots,b_N$. The following $K$ lines describe the matrix $S$. Each line contains a string of $K$ binary digits. For the $i$-th string from top to bottom, its $j$-th character is $S_{ij}$.

Output one integer, the minimum time required. If it is impossible to transmit the message from cow $1$ to cow $N$, output $-1$.

The optimal transmission sequence is $1 \to 4 \to 3 \to 5$. The total time is $|1-4|+|4-3|+|3-5|=6$. #### Test Point Properties: - Test points 1-5 satisfy $N \le 1000$. - Test points 6-13 have no additional constraints. Problem provided by: Dhruv Rohatgi Translated by ChatGPT 5