3564. [USACO21Jan Gold]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}$，并且如果品种 $i$ 的奶牛之间不愿意互相交流时可以有 $S_{ii} = 0$。

请求出传输信息所需的最小时间。

【输入格式】

输入的第一行包含 $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$。

【数据规模与约定】

测试点 1-5 满足 $N\le 1000$。

测试点 6-13 没有额外限制。

【来源】

USACO 一月公开赛 Gold 组