Telephone (USACO Gold 2021 January)

这显然是一个最短路径题，实际上直接上Dijkstra也可以得到大部分的分（93/100），但Naive Dijkstra的问题是没有利用距离是 $|i-j|$ 的条件，所以使得边的数量是 $n^2$ ，导致最大规模的时候TLE。

正解是用多层图上的0-1 BFS，把图的节点定义为(sender's breed, location)这个pair，从一个节点出发，可以任意左右移动，然后当到达一个愿意接收来自这个sender的消息的牛时，我们可以从(sender,loc)走到(receiver,loc)。这个效果上和原图等价，区别是节点变多（ $nK$ ），但边变少了（最多 $2nK$ ），而且边长更简单为 $0$ 或 $1$ ，所以可以使用0-1 BFS。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
 
// n <= 5e4, K <= 50
int n, K;
int b[50005];
char s[55][55];
int dist[55][50005];
 
int main() {
    scanf("%d %d", &n, &K);
    for (int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
        b[i]--;     // 0-based breed number
    }
    for (int i = 0; i < K; i++) {
        scanf("%s", s[i]);
        s[i][K] = s[i][b[n-1]];     // transmit to cow n-1
        s[i][K+1] = '\0';
    }
    b[n-1]=K;       // set cow n-1 to fake breed K
    for (int i = 0; i <= K; i++)
        for (int j = 0; j < n; j++)
            dist[i][j] = -1;
 
    deque<pii> q;   // sender's breed, location
    dist[b[0]][0] = 0;
    q.push_back({b[0],0});  
    while (!q.empty()) {
        int breed = q.front().first, loc = q.front().second;
        q.pop_front();
        // move left
        if (loc-1 >= 0 && dist[breed][loc-1]==-1) {
            dist[breed][loc-1] = dist[breed][loc] + 1;
            q.push_back({breed,loc-1});
        }
        // move right
        if (loc+1 < n && dist[breed][loc+1]==-1) {
            dist[breed][loc+1] = dist[breed][loc]+1;
            q.push_back({breed, loc+1});
        }
        // transmit to the cow at current loc
        if (s[breed][b[loc]] == '1' && dist[b[loc]][loc] == -1) {
            dist[b[loc]][loc] = dist[breed][loc];
            q.push_front({b[loc], loc});
        }
    }
    printf("%d", dist[K][n-1]);
    return 0;
}