题解 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;
}