题解 P1346 【电车】

钱逸凡

2018-04-24 14:09:05

Solution

很简单的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; } ```