#PU1090. USACO 2021 January Contest, Gold — Problem 2. Telephone
USACO 2021 January Contest, Gold — Problem 2. Telephone
USACO 2021 January Contest, Gold — Problem 2. Telephone
题目描述
Farmer John's cows, conveniently numbered , are standing in a line (). The th cow has a breed identifier in the range , with . The cows need your help to figure out how to best transmit a message from cow to cow . It takes time to transmit a message from cow to cow . However, not all breeds are willing to communicate with each other, as described by a matrix , where if a cow of breed is willing to transmit a message to a cow of breed , and otherwise. It is not necessarily true that , and it may even be the case that if cows of breed are unwilling to communicate with each-other. Please determine the minimum amount of time needed to transmit the message.
输入格式
The first line contains and . The next line contains space-separated integers . The next lines describe the matrix . Each consists of a string of bits, being the th bit of the th string from the top.
输出格式
Print a single integer giving the minimum amount of time needed. If it is impossible to transmit the message from cow to cow , then output .
数据范围
Test cases 1-5 satisfy . Test cases 6-13 satisfy no additional constraints. Problem credits: Dhruv Rohatgi
样例
样例 1
5 4
1 4 2 3 4
1010
0001
0110
0100
6
The optimal sequence of transmissions is $1\to 4\to 3\to 5$. The total amount of
time is $|1-4|+|4-3|+|3-5|=6$.