很神奇的转换
有N只猴子，第一只尾巴挂在树上，剩下的N-1只，要么被其他的猴子抓住，要么抓住了其他的猴子，要么两者均有。
当然一只猴子最多抓两只另外的猴子。
现在给出这N只猴子抓与被抓的信息，
并且在某个时刻可能某只猴子会放掉它其中一只手的猴子，导致某些猴子落地。
求每只猴子落地的时间。
luogu大佬原话：
事实上我们可以把猴子放手的时间当作这条边的边权，而不放手的边权为一个大数，
我们需要求得其实就是一条单源路径，让这条路径最小边权最大，直接输出这个值即可，
若这个值为那个大数，就输出-1。
一条路径最小边权就是断开时间
这个最大的 最小边权，就是到这个点的所有路径都断开的时间
#include<cstdio> #include<cstdlib> #include<cstring> #include<queue> using namespace std; int n,m; const int N=200003,M=N<<2; int ls[N],rs[N],tm[N][2]; int tot,head[N]; int ev[M],ew[M],enx[M]; void add(int u,int v,int w) { ev[++tot]=v,ew[tot]=w,enx[tot]=head[u],head[u]=tot; ev[++tot]=u,ew[tot]=w,enx[tot]=head[v],head[v]=tot; } int dis[N]; struct node { int v,dis; bool operator < (const node & o) const { return dis<o.dis; } }; priority_queue <node> q; void dijk() { dis[1]=m; q.push((node){1,m}); while(!q.empty() ) { node nw=q.top() ;q.pop() ; if(dis[nw.v ]!=nw.dis ) continue; for(int i=head[nw.v ];i;i=enx[i]) { int val=min(nw.dis ,ew[i]); if(dis[ev[i]] < val ) { dis[ev[i]]=val; q.push((node){ev[i],val}); } } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d%d",&ls[i],&rs[i]), tm[i][0]=tm[i][1]=m; for(int i=0;i<m;i++) { int x,fx; scanf("%d%d",&x,&fx); tm[x][fx-1]=i;//输入0 - m-1s放手情况 } for(int i=1;i<=n;i++) { if(ls[i]!=-1) add(i,ls[i],tm[i][0] ); if(rs[i]!=-1) add(i,rs[i],tm[i][1]); } //求0-m-1s掉落的猴子 dijk(); for(int i=1;i<=n;i++) if(dis[i]<m) printf("%d\n",dis[i]); else printf("-1\n"); return 0; }