Educational Codeforces Round 15 E Analysis of Pathes in Functional Graph(倍增)

题目链接
大意:给你一个有向图,每个点有且只有一个出边。
问你从所有点出发长经过k个点路径长度和,和最小边权。
倍增处理每个点出发跳 2 x 2^x 2x点的路径上的信息即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int n;
LL k;
LL f[N][55],w[N][55],m[N][55];
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>f[i][0];
    }
    memset(m,0x3f3f3f3f,sizeof m);
    for(int i=0;i<n;i++){
        cin>>w[i][0];
        m[i][0]=w[i][0];
    }
    for(int i=1;i<34;i++){
        for(int j=0;j<n;j++){
            f[j][i]=f[f[j][i-1]][i-1];
            w[j][i]=w[j][i-1]+w[f[j][i-1]][i-1];
            m[j][i]=min(m[j][i-1],m[f[j][i-1]][i-1]);
        }
    }
    for(int G=0;G<n;G++){
        LL MIN=1e18,sum=0;
        int r=G;
        for(int i=0;i<34;i++){
            if(k&(1ll<<i)){
                MIN=min(MIN,m[r][i]);
                sum+=w[r][i];
                r=f[r][i];
            }
        }
        cout<<sum<<' '<<MIN<<endl;
    }

    return 0;
}
全部评论

相关推荐

10-28 14:42
门头沟学院 Java
watermelon1124:因为嵌入式炸了
点赞 评论 收藏
分享
11-18 16:08
福州大学 Java
影流之主:干10年不被裁,我就能拿别人一年的钱了,日子有盼头了
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务