F - Lost Tree 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 800 点

出力する木の辺の重みに関する問題文の修正を行いました。ご迷惑をおかけして申し訳御座いません。(12:06)

問題文

ラスク君は木を持っていましたが、なくしてしまいました。

この木は、頂点に 1 以上頂点数以下の相異なる整数の番号がついていて、各辺には 1 以上 10^9 以下の整数の重みが定まっていました。

頂点数は K 以上 1000 以下であり、1 \leq i, j \leq K に対し、頂点 i と頂点 j の距離は D_{ij} でした。ただし、頂点 i と頂点 j の距離とは、頂点 i と頂点 j を結ぶ単純パスに含まれる辺の重みの総和のことをいいます。

これらの情報から、ラスク君の持っていた木として考えられるものを一つ出力してください。なお、この問題で与えられる入力に対しては、いずれも条件に整合する木が少なくとも一つ存在することが保証されています。

制約

  • 入力はすべて整数である。
  • 2 \leq K \leq 300
  • i < j のとき 1 \leq D_{ij} \leq 10^9
  • D_{ij}=D_{ji}
  • D_{ii}=0
  • 問題文の条件を満たす木が少なくとも 1 つ存在する。

入力

入力は以下の形式で標準入力から与えられる。

K
D_{11} D_{12} \ldots D_{1K}
D_{21} D_{22} \ldots D_{2K}
:
D_{K1} D_{K2} \ldots D_{KK}

出力

ラスク君の持っていた木として考えられるものを一つ、次の形式で出力せよ。

N
a_1 b_1 c_1
a_2 b_2 c_2
:
a_{N-1} b_{N-1} c_{N-1}

頂点数が N で、頂点 a_i と頂点 b_i を重み c_i の辺でつないでできるグラフが条件を満たす木になるとき、正解となる。

条件を満たす木が複数考えられる場合、どれを出力してもよい。

ただし、c_i の値は 1 以上 10^9 以下の整数である必要があります。

入力例 1

4
0 3 4 5
3 0 5 6
4 5 0 7
5 6 7 0

出力例 1

5
1 5 1
4 5 4
5 2 2
5 3 3

例えば、下図のような木が条件を満たします。

入力例 2

3
0 2 3
2 0 5
3 5 0

出力例 2

4
1 4 1
1 2 2
4 3 2

例えば、下図のような木が条件を満たします。

入力例 3

5
0 5 6 3 5
5 0 7 6 6
6 7 0 7 3
3 6 7 0 6
5 6 3 6 0

出力例 3

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