分数: 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