Telephone

题目描述

Farmer John 的 $N$ 头奶牛（方便起见编号为 $1 \ldots N$）站成一排（$1\le N\le 5\cdot 10^4$）。第 $i$ 头奶牛的品种标识为 $b_i$，范围在 $1 \ldots K$，其中 $1\le K\le 50$。奶牛们需要你帮助确定，如何以最佳方式将一条消息从奶牛 $1$ 传递到奶牛 $N$。

从奶牛 $i$ 向奶牛 $j$ 传递消息需要 $|i-j|$ 的时间。然而，并非所有品种之间都愿意相互通信，这由一个 $K \times K$ 的矩阵 $S$ 描述：当品种为 $i$ 的奶牛愿意向品种为 $j$ 的奶牛传递消息时，$S_{ij} = 1$，否则为 $0$。不一定有 $S_{ij}=S_{ji}$，甚至可能出现 $S_{ii} = 0$，表示品种为 $i$ 的奶牛彼此之间也不愿通信。

请确定传递该消息所需的最少时间。

输入格式

第一行包含 $N$ 和 $K$。 下一行包含 $N$ 个以空格分隔的整数 $b_1,b_2,\ldots,b_N$。 接下来的 $K$ 行描述矩阵 $S$。每行由一个长度为 $K$ 的二进制字符串组成，其中从上往下第 $i$ 行字符串的第 $j$ 位表示 $S_{ij}$。

输出格式

输出一个整数，表示所需的最少时间。 如果无法将消息从奶牛 $1$ 传递到奶牛 $N$，则输出 $-1$。

5 4
1 4 2 3 4
1010
0001
0110
0100

6

提示

最优的传递序列为 $1\to 4\to 3\to 5$。总时间为 $|1-4|+|4-3|+|3-5|=6$。 SCORING: 测试点 1-5 满足 $N\le 1000$。 测试点 6-13 无额外限制。 题目来源：Dhruv Rohatgi

标签: USACO|2021|Gold

来源

USACO|2021|Gold