yukicoder 1399 すごろくで世界旅行 (構築)
まず$ D = 1の場合について考える. この場合, 1ターンで必ずすべての頂点にたどり着けないといけないため, 行列の要素をすべて1にするしかない.
それ以外の$ D \geq 2の場合について考える. ここで逆から考える. すると$ D - 1ターン後から$ Dターン目について, ある頂点にすべての頂点を集めることができればそこから$ V辺ですべての頂点にたどり着くことができることがわかる. よって最初のターンに頂点1にすべての頂点を集め, 頂点1から頂点1に辺を張って"時間稼ぎ"することにより最後のターンですべての頂点に少ない辺でたどり着くことができることがわかる. まとめると, $ i = 0または$ j = 0のなる行列の要素を1, それ以外を0とすればよい. これが最適解である.