题目背景

点我跳转至洛谷

做完后记得选择这个选择题。 {{ select(1) }}

• 提交并且通过了

题目描述

有一个 $n$ 个点 $n$ 条边的带权有向图（点编号 $0\sim n-1$），每个点有且仅有一条出边，对于每个点 $i$ 求出由 $i$ 出发走过 $k$ 条边，这 $k$ 条边权值的最小值与这 $k$ 条边权值之和。

输入格式

第一行两个正整数 $n$ 和 $k$。

第二行 $n$ 个正整数，第 $i$ 个数表示点 $i$ 的出边指向的点。

第三行 $n$ 个正整数，第 $i$ 个数表示点 $i$ 的出边的权值。

输出格式

共 $n$ 行，每行两个数，第一个数表示由点 $i$ 出发经过 $k$ 条边，这 $k$ 条边的权值和，第二个数表示最小值。

7 3
1 2 3 4 3 2 6
6 3 1 4 2 2 3

10 1
8 1
7 1
10 2
8 2
7 1
9 3

4 4
0 1 2 3
0 1 2 3

0 0
4 1
8 2
12 3

5 3
1 2 3 4 0
4 1 2 14 3

7 1
17 1
19 2
21 3
8 1

样例 1 解释

数据范围

$1\leq n\leq 10^5$，$1\leq k\leq 10^{10}$，$0\leq f_i<n$，$0\leq w_i\leq 10^8$