记录编号	603152	评测结果	AAAAAAAAAAAAA
题目名称	3564.[USACO21Jan Gold]Telephone	最终得分	100
用户昵称	Ruyi	是否通过	通过
代码语言	C++	运行时间	0.169 s
提交时间	2025-07-09 14:30:19	内存使用	4.04 MiB

#include<bits/stdc++.h>
using namespace std;
int n,k,a[50005],s[55][55],dis[50005];
char c;
vector<int> b[55];
queue<int> q;
void f(){
    for(int i=2;i<=n;i++) dis[i]=1e9;
    q.push(k+1);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v=1;v<=k+2;v++){
            if(!s[u][v]) continue;
            bool flag=false;
            for(int i=0,j=0;i<b[u].size()&&j<b[v].size();){
                if(dis[b[u][i]]+abs(b[u][i]-b[v][j])<dis[b[v][j]]){
                    dis[b[v][j]]=dis[b[u][i]]+abs(b[u][i]-b[v][j]);
                    flag=true;
                }
				if(i==b[u].size()-1||b[u][i]>b[v][j]) j++;
				else i++;
            }
            if(flag) q.push(v);
        }
    }
    return ;
}
int main(){
    freopen("telephone.in","r",stdin);
    freopen("telephone.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=k;i++)
	for(int j=1;j<=k;j++){
	    cin>>c;
	    s[i][j]=c-'0';
    }
    for(int i=2;i<n;i++) b[a[i]].push_back(i);
    b[k+1].push_back(1);
    b[k+2].push_back(n);
    if(a[1]==a[n]&&s[a[1]][a[n]]){
        cout<<n-1<<endl;
        return 0;
    }
    for(int i=1;i<=k;i++){
        s[k+1][i]=s[a[1]][i];
        s[i][k+2]=s[i][a[n]];
    }
    a[1]=k+1;
    a[2]=k+2;
    f();
    if(dis[n]!=1e9) cout<<dis[n]<<endl;
    else cout<<-1<<endl;
	return 0;
}