上一波题目 https://www.luogu.org/problem/P1346
是道水题 路口一开始对着的那条路权值为0 其余路权值为1 然后跑一遍最短路就好了
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cmath> #define inf 1e9 using namespace std; const int M=1e5+7; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } int n,Ts,Td; int first[M],cnt; struct node{int to,next,w;}e[2*M]; void ins(int x,int y,int w){e[++cnt]=(node){y,first[x],w}; first[x]=cnt;} struct qwq{ int id,d; bool operator<(const qwq&x)const{return x.d<d;} }; int dis[M]; priority_queue<qwq>q; void dj(){ for(int i=1;i<=n;i++) dis[i]=inf; dis[Ts]=0; q.push((qwq){Ts,dis[Ts]}); while(!q.empty()){ qwq x=q.top(); q.pop(); if(x.d<dis[x.id]) continue; for(int i=first[x.id];i;i=e[i].next){ int now=e[i].to; if(dis[now]>dis[x.id]+e[i].w){ dis[now]=dis[x.id]+e[i].w; q.push((qwq){now,dis[now]}); } } } } int main(){ int k,x; n=read(); Ts=read(); Td=read(); for(int i=1;i<=n;i++){ k=read(); for(int j=1;j<=k;j++){ x=read(); if(j==1) ins(i,x,0); else ins(i,x,1); } } dj(); if(dis[Td]==inf) puts("-1"); else printf("%d\n",dis[Td]); return 0; }