警示后人
查看原帖
警示后人
1036832
qiucr楼主2024/8/8 21:10

如果你用的是倍增跳的话,记fa[u][k]表示从u开始跳2k2^k步到的点,st[u][k]表示从u开始跳2k2^k步经过的边权,那么你要先算st,再跳
上面那个是对的,下面那个是错的

int get(int s,ll t){
    for(int k=20;k>=0;k--){
        if(fa[s][k]&&st[s][k]<=t){
            t-=st[s][k],s=fa[s][k];
        }
    }
    return s;
}
int get(int s,ll t){
    for(int k=20;k>=0;k--){
        if(fa[s][k]&&st[s][k]<=t){
            s=fa[s][k],t-=st[s][k];
        }
    }
    return s;
}
2024/8/8 21:10
加载中...