플루이드 워샬 알고리즘 참고
import java.util.Scanner;
public class 사람네트워크 {
static int T , N;
static final int INF = 999999;
static int adjMatrix[][];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int tc = 1; tc<=T; tc++) {
N = sc.nextInt();
adjMatrix = new int[N][N];
for(int i =0; i<N; ++i) {
for(int j =0; j<N; ++j ) {
adjMatrix[i][j] = sc.nextInt();
if(i !=j && adjMatrix[i][j] == 0) {
adjMatrix[i][j] = INF;
}
}
}
for(int k =0; k<N; ++k) {
for(int i =0; i<N; ++i) {
if(i==k) continue; // 이건 자기 자신을 경우에서 가니까 빼준다
for(int j =0; j<N; ++j) {
if(i==j || k==j) continue;
if(adjMatrix[i][j] > adjMatrix[i][k] + adjMatrix[k][j]) {
adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
}
}
}
}
int min = 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<min) {
min = sum;
}
}
System.out.println("#" + tc + " " + min);
}
}
}
'알고리즘 > SwExpert recipe' 카테고리의 다른 글
[SWEA] 민석이의 과제제출하기 [D3] (0) | 2021.03.29 |
---|---|
[SWEA] 직사각형 길이 찾기 [D3] (0) | 2021.03.29 |
[SWEA] 준홍이의카드놀이 D3 (0) | 2021.03.25 |
[SWEA] 동철이의 프로그래밍 대회 D3 (0) | 2021.03.20 |
[SWEA] String D3 (0) | 2021.03.20 |