提交时间:2024-04-06 21:34:32

运行 ID: 142294

#include<bits/stdc++.h> using namespace std; const int maxn=1e6+99; int n,tot,head[maxn],vis[maxn],dis[maxn],a,x,y; struct edge{ int to,next,w; }e[maxn]; void add(int a,int b,int w){ e[++tot].to=b; e[tot].next=head[a]; e[tot].w=w; head[a]=tot; } void Spfa(int x){ memset(dis,0x3f,sizeof(dis)); dis[x]=0; vis[x]=1; queue<int> q; q.push(x); while(!q.empty()){ int tmp=q.front(); q.pop(); vis[tmp]=0; for(int i=head[tmp];i;i=e[i].next){ if(dis[tmp]+e[i].w<dis[e[i].to]){ dis[e[i].to]=dis[tmp]+e[i].w; if(!vis[e[i].to])q.push(e[i].to),vis[e[i].to]=1; } } } } int main(){ cin>>n>>x>>y; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ cin>>a; if(a==1)add(i,j,1),add(j,i,1); } if(x==y){cout<<0;return 0;} Spfa(x); if(dis[y]==0x3f3f3f3f)cout<<0; else cout<<dis[y]-1; return 0; }