Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
142294 | baim. | 人际关系 | C++ | 通过 | 100 | 3 MS | 4184 KB | 863 | 2024-04-06 21:34:32 |
#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; }