문제 설명
주어진 가중치 방향 그래프에서 최적 일주여행경로를 찾아 주세요. 이 그래프에서 가중치는 음이 아닌 정수입니다.
입력 설명
첫 줄에는 테스트케이스 T(1<=T<=100)가 주어집니다. 각 테스트케이스마다 첫 줄에는 그래프의 노드 수 N(3<=N<=20)가 주어지고, 그다음 N개 줄에 0번째 노드부터 다른 노드까지 간선의 가중치 W(0<=W<=100)가 주어집니다. 만약 노드 v에서 노드 w가 없으면 가중치로 -1이 주어집니다. 노드 v에서 노드 v로의 간선은 존재하지 않지만 가중치를 0으로 주어집니다.
출력 설명
각 테스트케이스마다 최적 일주여행경로의 길이를 출력하여 주세요.
2
5
0 14 4 10 20
14 0 7 8 7
4 5 0 7 16
11 7 9 0 2
18 7 17 4 0
4
0 2 9 -1
1 0 6 4
-1 7 0 8
6 3 -1 0