记录编号	603147	评测结果	AAAAAMAMAAMAA
题目名称	3564.[USACO21Jan Gold]Telephone	最终得分	77
用户昵称	对立猫猫对立	是否通过	未通过
代码语言	C++	运行时间	2.301 s
提交时间	2025-07-09 14:25:09	内存使用	103.12 MiB

#include <bits/stdc++.h>
using namespace std;
int N, K;
vector<pair<int, int> > g[50005];
short b[50005];
vector<int> color[55];
int d[50005];
bool vis[50005];
void spfa(int s) {
  memset(d, 0x3f, sizeof(d));
  memset(vis, 0, sizeof(vis));
  deque<int> q;
  q.push_back(s);
  vis[s] = true;
  d[s] = 0;
  while (!q.empty()) {
    int x = q.front();
    q.pop_front();
    vis[x] = 0;
    for (int i = 0; i < g[x].size(); i++) {
      int y = g[x][i].first, w = g[x][i].second;
      if (d[y] > d[x] + w) {
        d[y] = d[x] + w;
        if (!vis[y]) {
          if(!q.empty() && d[y] <= d[q.front()]) q.push_front(y);
          else q.push_back(y);
          if(!q.empty() && d[q.front()] > d[q.back()]) swap(q[0], q[q.size() - 1]);
          vis[y] = 1;
        }
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  //freopen("telephone.in", "r", stdin);
  //freopen("telephone.out", "w", stdout);
  cin >> N >> K;
  for(int i = 1; i <= N; i++) cin >> b[i], color[b[i]].push_back(i);
  for(int i = 1; i <= K; i++) {
    for(int j = 1; j <= K; j++) {
      char ch;
      cin >> ch;
      if(ch - '0') {
        for(int k = 0; k < color[i].size(); k++) {
          for(int l = 0; l < color[j].size(); l++) {
            g[color[i][k]].push_back({color[j][l], abs(color[i][k] - color[j][l])});
          }
        }
      }
    }
  }
  spfa(1);
  if(d[N] == 0x3f3f3f3f) cout << -1 << endl;
  else cout << d[N] << endl;
  return 0;
}