← 返回题目列表

AtCoder · abc445_f

F. 正好 K 个步骤 2

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有一个有向图 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,找到遍历的边的最小可能总成本。更正式地说,找到最小可能值 \displaystyle\sum_{i=1}^{K}C_{v_{i-1},v_i} 序列 v=(v_0,v_1,\ldots,v_K) 之间的整数 1 和 N,包含在内,长度 K+1 满意 v_0=v_K=s.

约束

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

输入

输入由标准输入按以下格式给出:

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 \le i \le N) 应包含问题的答案 s=i.


示例输入 1

4 3
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3

示例输出 1

8
8
8
9

对于 s=1, 移动 1\rightarrow2\rightarrow3\rightarrow1 给出的总成本为 1+2+5=8。 不可能从顶点开始 1,沿一条边移动 3 次,总成本为 7 或更少,因此打印 8 在第一行。

对于 s=4, 移动 4\rightarrow4\rightarrow4\rightarrow4 给出的总成本为 3+3+3=9。 请注意,同一条边或同一个顶点可能会被遍历多次,如果同一条边被遍历多次,则其成本将被添加到总次数中。


示例输入 2

3 1000000000
100 999 999
999 100 999
999 999 100

示例输出 2

100000000000
100000000000
100000000000

答案可能是 2^{32} 或更大。


示例输入 3

10 9482
748 169 586 329 972 529 432 519 408 587
138 249 656 114 632 299 984 755 404 772
155 506 832 854 353 465 387 374 567 385
631 556 951 428 104 705 530 406 258 102
709 325 334 193 520 798 749 582 337 910
530 110 659 635 786 773 811 468 810 638
111 822 554 627 395 959 924 698 777 893
142 848 532 781 711 814 665 395 960 290
746 266 603 553 893 353 323 640 172 263
749 921 845 334 594 821 233 695 109 951

示例输出 3

1382481
1382481
1382628
1382481
1382481
1382540
1382481
1382739
1382499
1382481