A999电话 全站首发题解

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

const long long INF = 1e18;
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n, k;
    std::cin >> n >> k;
    std::vector<int> b(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> b[i];
        b[i]--;
    }
    std::vector<std::vector<bool>> s(k, std::vector<bool>(k));
    for (int i = 0; i < k; ++i) {
        std::string row;
        std::cin >> row;
        for (int j = 0; j < k; ++j) {
            s[i][j] = (row[j] == '1');
        }
    }
    std::vector<long long> dist(n, INF);
    dist[0] = 0;
    for (int iter = 0; iter < k; ++iter) {
        std::vector<std::vector<long long>> temp_prefix_A(k, std::vector<long long>(n, INF));
        for (int p = 0; p < k; ++p) {
            long long min_val = INF;
            for (int i = 0; i < n; ++i) {
                if (b[i] == p && dist[i] != INF) {
                    min_val = std::min(min_val, dist[i] - i);
                }
                temp_prefix_A[p][i] = min_val;
            }
        }
        std::vector<std::vector<long long>> temp_suffix_B(k, std::vector<long long>(n, INF));
        for (int p = 0; p < k; ++p) {
            long long min_val = INF;
            for (int i = n - 1; i >= 0; --i) {
                if (b[i] == p && dist[i] != INF) {
                    min_val = std::min(min_val, dist[i] + i);
                }
                temp_suffix_B[p][i] = min_val;
            }
        }
        std::vector<long long> new_dist = dist;
        for (int i = 0; i < n; ++i) {
            int target_breed = b[i];
            long long min_from_any_breed = INF;
            for (int source_breed = 0; source_breed < k; ++source_breed) {
                if (s[source_breed][target_breed]) {
                    long long cost_from_left = INF;
                    if (i > 0 && temp_prefix_A[source_breed][i - 1] != INF) {
                        cost_from_left = (long long)i + temp_prefix_A[source_breed][i - 1];
                    }
                    long long cost_from_right = INF;
                    if (i < n - 1 && temp_suffix_B[source_breed][i + 1] != INF) {
                        cost_from_right = (long long)-i + temp_suffix_B[source_breed][i + 1];
                    }
                    min_from_any_breed = std::min({min_from_any_breed, cost_from_left, cost_from_right});
                }
            }
            new_dist[i] = std::min(new_dist[i], min_from_any_breed);
        }
        dist = new_dist;
    }
    if (dist[n - 1] == INF) {
        std::cout << -1 << std::endl;
    } else {
        std::cout << dist[n - 1] << std::endl;
    }
    return 0;
}