/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
頂点 1, 頂点 2,\ldots, 頂点 N の N 頂点からなる有向グラフがあります。 1 以上 N 以下の任意の整数の 2 つ組 (i,j) について、頂点 i から頂点 j への有向辺がちょうど 1 本存在し、そのコストは C _ {i,j} です。
正整数 K が与えられます。 s=1,2,\ldots,N のそれぞれについて、以下の問題を解いてください。
- 頂点 s から出発し、辺に沿って移動することを K 回繰り返して頂点 s へ向かう方法のうち、通った辺のコストの総和としてありうる最小値を求めよ。厳密には、v _ 0=v _ K=s を満たす 1 以上 N 以下の整数からなる長さ K+1 の列 v=(v _ 0,v _ 1,\ldots,v _ K) に対する \displaystyle\sum _ {i=1} ^ {K}C _ {v _ {i-1},v _ i} の総和としてありうる最小値を求めよ。
制約
- 1\le N\le100
- 1\le K\le10 ^ 9
- 0\le C _ {i,j}\le10 ^ 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 以下にすることはできないため、1 行目には 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
Score : 500 points
Problem Statement
There is a directed graph with N vertices, vertex 1, vertex 2,\ldots, vertex N. For any pair of integers (i,j) with 1 \leq i,j \leq N, there is exactly one directed edge from vertex i to vertex j with cost C_{i,j}.
You are given a positive integer K. For each of s=1,2,\ldots,N, solve the following problem.
- Among the ways to start at vertex s, move along an edge K times, and return to vertex s, find the minimum possible total cost of the edges traversed. More formally, find the minimum possible value of \displaystyle\sum_{i=1}^{K}C_{v_{i-1},v_i} for a sequence v=(v_0,v_1,\ldots,v_K) of integers between 1 and N, inclusive, of length K+1 satisfying v_0=v_K=s.
Constraints
- 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)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
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}
Output
Output N lines. The i-th line (1 \le i \le N) should contain the answer to the problem for s=i.
Sample Input 1
4 3 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3
Sample Output 1
8 8 8 9
For s=1, moving 1\rightarrow2\rightarrow3\rightarrow1 gives a total cost of 1+2+5=8.
It is impossible to start at vertex 1, move along an edge three times, and achieve a total cost of 7 or less, so print 8 on the first line.
For s=4, moving 4\rightarrow4\rightarrow4\rightarrow4 gives a total cost of 3+3+3=9. Note that the same edge or the same vertex may be traversed multiple times, and if the same edge is traversed multiple times, its cost is added to the total that many times.
Sample Input 2
3 1000000000 100 999 999 999 100 999 999 999 100
Sample Output 2
100000000000 100000000000 100000000000
The answer may be 2^{32} or greater.
Sample Input 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
Sample Output 3
1382481 1382481 1382628 1382481 1382481 1382540 1382481 1382739 1382499 1382481