题解 P1346 【电车】
钱逸凡
2018-04-24 14:09:05
很简单的spfa,只要注意不要重复搜即可。
注意到不了的要输出-1
c++AC代码
```
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int Read(){
int x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}//读写优化是个好习惯
int n,a,b;
struct way{
int k;
int zhong[101];
}dian[101];//与每个点相连的路
queue <int > q;
int dist[101];
int inque[101];
int vis[101];
void spfa(int s){
memset(dist,0x3f,sizeof(dist));//初始化
dist[s]=0;
q.push(s);
inque[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
inque[u]=0;
if(vis[u]==0)
for(int i=1;i<=dian[u].k;i++){
if(i==1){
dist[dian[u].zhong[1]]=min(dist[dian[u].zhong[1]],dist[u]);
}//不按开关
else if(dist[u]+1<dist[dian[u].zhong[i]]){
dist[dian[u].zhong[i]]=dist[u]+1;
}//按开关且比原来次数少
if(inque[dian[u].zhong[i]]==0){
inque[dian[u].zhong[i]]=1;
q.push(dian[u].zhong[i]);
}
}//防止重复入队
vis[u]=1;//防止重复搜同一个点
}
}
int main(){
n=Read(),a=Read(),b=Read();
int i,j;
for(i=1;i<=n;i++){
dian[i].k=Read();
for(j=1;j<=dian[i].k;j++)dian[i].zhong[j]=Read();
}
spfa(a);
if(dist[b]==1061109567)printf("-1");//到不了
else printf("%d",dist[b]);
return 0;
}
```