题解 P1653 【猴子 】

看到下面都是逆序连边用并查集ac，这里蒟蒻就来一波spfa，事实上我们可以把猴子放手的时间当作这条边的边权，而不放手的边权为一个大数，我们需要求得其实就是一条单源路径，让这条路径最小边权最大，直接输出这个值即可，若这个值为那个大数，就输出-1。而这个其实就跟单源最短路差不多，用SPFA就能~~轻松~~通过。 ``` #include<bits/stdc++.h> using namespace std; const int N=1e6; int a[N],ans[N],l[2][N],r[2][N],to[N],nex[N],w[N],degree[N],n,m; void SPFA() { queue<int>q; q.push(1); while(!q.empty()){ int u=q.front();q.pop(); for(int i=a[u];i;i=nex[i]){ int v=to[i],W=min(ans[u],w[i]); if(W>ans[v]){ans[v]=W;q.push(v);} } } } int main(){ cin>>n>>m; for(int i=1,t=1;i<=n;++i){scanf("%d%d",&l[1][i],&r[1][i]);l[0][i]=m,r[0][i]=m;} ans[1]=m; for(int i=0;i<m;++i){ int x,y; scanf("%d%d",&x,&y); if(y==1)l[0][x]=min(i,l[0][x]); if(y==2)r[0][x]=min(i,r[0][x]); } for(int i=1,t=0;i<=n;++i){ int x=l[1][i],y=r[1][i]; if(x!=-1){ nex[++t]=a[i],to[t]=x,w[t]=l[0][i],a[i]=t; nex[++t]=a[x],to[t]=i,w[t]=l[0][i],a[x]=t; } if(y!=-1){ nex[++t]=a[i],to[t]=y,w[t]=r[0][i],a[i]=t; nex[++t]=a[y],to[t]=i,w[t]=r[0][i],a[y]=t; } } SPFA(); for(int i=1;i<=n;++i) if(ans[i]==m)printf("-1\n"); else printf("%d\n",ans[i]); return 0; } ```