Educational Codeforces Round 15 E. Analysis of Pathes in Functio(每个点走k步会到达哪个点,经过的边中的最小值是多少,经过的边的权值和)

传送门:Educational Codeforces Round 15 E. Analysis of Pathes in Functio

题意:给你一个n和k,然后每个点连出去一条边,接下来的每条边的权值,问每个点走k步会到达哪个点,经过的边中的最小值是多少,经过的边的权值和

思路:因为每个点连出去一条边,所以肯定会有环,而且每个点走k步一定能走到某个点,而且这个点是唯一确定的,
那么利用倍增简单搞搞就行了

#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf -0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
#define MP(x,y) make_pair(x,y)
typedef long long ll;
void fre() { freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); }
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
typedef pair<int,int> PI;
const int maxn=100100;
int minv[maxn][50],dp[maxn][50];
long long sum[maxn][50];
int net[maxn],len[maxn];
int ans_minv[maxn],cur[maxn];
long long ans_sum[maxn];

int main(){
    int n,cnt=0;
    long long k,num=1;
    scanf("%d%lld",&n,&k);
    for(int i=0;i<n;i++)    scanf("%d",&net[i]);
    for(int i=0;i<n;i++)    scanf("%d",&len[i]);
    for(int i=0;i<n;i++)   dp[i][0]=net[i],minv[i][0]=sum[i][0]=len[i];
    while(num<=k)
        num<<=1,cnt++;
    for(int i=0;i<n;i++)    cur[i]=i,ans_minv[i]=INF,ans_sum[i]=0;
    for(int i=1;i<=cnt;i++)
        for(int j=0;j<n;j++){
            sum[j][i]=sum[j][i-1]+sum[dp[j][i-1]][i-1];
            minv[j][i]=min(minv[j][i-1],minv[dp[j][i-1]][i-1]);
            dp[j][i]=dp[dp[j][i-1]][i-1];
        }
    for(int now=0;now<=cnt;now++)
        if((k>>now)&1){
            for(int i=0;i<n;i++){
                ans_minv[i]=min(ans_minv[i],minv[cur[i]][now]);
                ans_sum[i]+=sum[cur[i]][now];
                cur[i]=dp[cur[i]][now];
            }
        }
    for(int i=0;i<n;i++)
        printf("%lld %d\n",ans_sum[i],ans_minv[i]);
    return 0;
}