직무 조회

줄리아의 친구 $n$명은 이사 간 새로운 나라에서 스타트업을 꾸리려고 한다. 이들은 맡은 직무에 따라 1부터 $n$까지 번호를 매겼다. 번호는 프런트엔드 업무에 가까운 직무부터 백엔드 업무에 가까운 직무 순서이다. 또한 행렬 $c$를 추정했다. $c_{ij} = c_{ji}$는 직무 $i$를 맡은 사람과 직무 $j$를 맡은 사람 사이에서 월평균 오가는 메시지 수이다.

이제 계층 트리를 만들려고 한다. 이 트리는 이진 트리이며, 각 노드에는 팀원 한 명이 들어간다. 팀의 리더로 뽑힌 팀원은 루트 노드에 들어간다. 리더가 모든 부하 팀원에게 쉽게 닿을 수 있도록, 트리의 각 노드 $v$에 대해 다음 조건을 지켜야 한다. $v$의 왼쪽 서브트리에 있는 팀원의 번호는 모두 $v$보다 작아야 하고, 오른쪽 서브트리에 있는 팀원의 번호는 모두 $v$보다 커야 한다.

계층 트리가 정해지면, 직무 $i$와 직무 $j$를 맡은 사람들은 트리에서 두 노드 사이의 최단 경로를 통해 연락한다. 이 경로의 길이를 $d_{ij}$라고 하자. 그러면 두 사람의 연락 비용은 $c_{ij} \cdot d_{ij}$이다.

모든 쌍에 대한 연락 비용의 합 $\sum_{1 \le i < j \le n} c_{ij} \cdot d_{ij}$를 최소로 만드는 계층 트리를 찾으시오.

첫 줄에는 스타트업을 조직하는 팀원의 수 $n$ ($1 \le n \le 200$)이 주어진다.

다음 $n$개의 줄에는 각각 정수 $n$개가 주어진다. $i$번째 줄의 $j$번째 수는 $c_{ij}$이며, 팀원 $i$와 $j$ 사이에서 월평균 오가는 메시지 수의 추정치이다 ($0 \le c_{ij} \le 10^9$; $c_{ij} = c_{ji}$; $c_{ii} = 0$).

연락 비용의 합을 최소로 만드는 계층 트리를 출력한다. 1부터 $n$까지 각 팀원에 대해, 부모 노드의 번호를 출력한다. 리더는 0을 출력한다. 최적의 트리가 여러 개라면, 그중 아무거나 하나를 출력하면 된다.

가능한 최소 총비용은 $566 \cdot 1+239 \cdot 1+30 \cdot 1+1 \cdot 2+1 \cdot 2=839$이다: