#PU1090. USACO 2021 January Contest, Gold — Problem 2. Telephone

    ID: 1480 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan21来源:usaco.orgscoring:equal_test_cases广搜

USACO 2021 January Contest, Gold — Problem 2. Telephone

USACO 2021 January Contest, Gold — Problem 2. Telephone

题目描述

Farmer John's NN cows, conveniently numbered 1…N1 \ldots N, are standing in a line (1≤N≤5⋅1041\le N\le 5\cdot 10^4). The iith cow has a breed identifier bib_i in the range 1…K1 \ldots K, with 1≤K≤501\le K\le 50. The cows need your help to figure out how to best transmit a message from cow 11 to cow NN. It takes ∣i−j∣|i-j| time to transmit a message from cow ii to cow jj. However, not all breeds are willing to communicate with each other, as described by a K×KK \times K matrix SS, where Sij=1S_{ij} = 1 if a cow of breed ii is willing to transmit a message to a cow of breed jj, and 00 otherwise. It is not necessarily true that Sij=SjiS_{ij}=S_{ji}, and it may even be the case that Sii=0S_{ii} = 0 if cows of breed ii are unwilling to communicate with each-other. Please determine the minimum amount of time needed to transmit the message.

输入格式

The first line contains NN and KK. The next line contains NN space-separated integers b1,b2,…,bNb_1,b_2,\ldots,b_N. The next KK lines describe the matrix SS. Each consists of a string of KK bits, SijS_{ij} being the jjth bit of the iith 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 11 to cow NN, then output −1-1.

数据范围

Test cases 1-5 satisfy N≤1000N\le 1000. 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$.