인접행렬로 입력을 받고, 직접 연결되지 않은 정점에 대한 인접행렬 값을 간선의 수로 갱신한다.
각 행의 합 중 최소값을 찾아 출력하면 문제에서 원하는 답을 구할 수 있다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Solution {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
public static void main(String[] args) throws IOException {
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int[][] adjMatrix = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
adjMatrix[i][j] = Integer.parseInt(st.nextToken());
if (i != j && adjMatrix[i][j] == 0)
adjMatrix[i][j] = Integer.MAX_VALUE / 3;
}
}
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
if (k == i)
continue;
for (int j = 0; j < N; j++) {
if (i == j || j == k)
continue;
if (adjMatrix[i][j] > adjMatrix[i][k] + adjMatrix[k][j]) { // k를 경유한 경우 더 짧으면 갱신.
adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
}
}
}
}
/* for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
bw.append(adjMatrix[i][j] +" ");
}
bw.append("\n");
}*/
int answer = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
int sum = 0;
for (int j = 0; j < N; j++) {
sum += adjMatrix[i][j];
}
if (sum < answer) {
answer = sum;
}
}
bw.append("#" + tc + " " + answer + "\n");
}
bw.flush();
}
}