AT_abc445_f.[ABC445F] Exactly K Steps 2

有一个包含 $N$ 个顶点的有向图，顶点依次编号为 $1,2,\ldots,N$。对于任意整数对 $(i,j)$，$1\leq i,j\leq N$，都存在一条从顶点 $i$ 到顶点 $j$ 的有向边，其代价为 $C_{i,j}$。

你将获得一个正整数 $K$。对于每个 $s=1,2,\ldots,N$，需要你解决下列问题。

• 从顶点 $s$ 出发，连续走 $K$ 步（每一步按照有向边移动），最终回到顶点 $s$ 的所有路径中，找出经过的边的总代价的最小值。更正式地说，即求满足 $v_0=v_K=s$ 的整数序列 $v=(v_0,v_1,\ldots,v_K)$，其中每个 $v_i$ 满足 $1\leq v_i\leq N$，使得 $\displaystyle\sum_{i=1}^K C_{v_{i-1}, v_i}$ 取得最小值。

输入通过标准输入给出，格式如下：

$N\ K$
$C_{1,1}\ C_{1,2}\ \ldots\ C_{1,N}$
$C_{2,1}\ C_{2,2}\ \ldots\ C_{2,N}$
$\vdots$
$C_{N,1}\ C_{N,2}\ \ldots\ C_{N,N}$

输出共 $N$ 行。第 $i$ 行 ($1\leq i\leq N$) 应输出对于 $s=i$ 时要求的最小总代价。

样例解释 1

对于 $s=1$，沿着路径 $1\rightarrow2\rightarrow3\rightarrow1$ 移动，总代价为 $1+2+5=8$。无法通过从顶点 $1$ 出发，经过三次边，回到 $1$ 并使总代价小于等于 $7$，因此第一行输出应为 8。

对于 $s=4$，沿着路径 $4\rightarrow4\rightarrow4\rightarrow4$ 移动，总代价为 $3+3+3=9$。注意可以多次经过相同的边或顶点，每经过一次，相应的代价要重复累加。

样例解释 2

答案可能会大于等于 $2^{32}$。

数据范围

• $1 \leq N \leq 100$
• $1 \leq K \leq 10^9$
• $0 \leq C_{i,j} \leq 10^9\ (1 \leq i \leq N,1 \leq j \leq N)$
• 所有输入值均为整数。

由 ChatGPT 5 翻译