[D6] 1263. [S/W 문제해결 응용] 8일차 - 사람 네트워크2

#include <stdio.h>
#include <stdlib.h>
#include <string>
using namespace std;
int graph[1020][1020] = { 0 };


int main(void) {

	int test_case = 0;
	scanf("%d", &test_case);

	for (int i = 0; i < test_case; i++) {
		int person_number = 0;
		
		scanf("%d", &person_number);
		for (int n = 0; n < person_number; n++) {
			for (int m = 0; m < person_number; m++) {
				scanf("%d", &graph[n][m]);
				if (graph[n][m] == 0)
					graph[n][m] = 100000;
				if (n == m)
					graph[n][m] = 0;
			}
		}
		for (int k = 0; k < person_number; k++)
			for (int i =0; i < person_number; i++)
				for (int j = 0; j < person_number; j++)
					if (graph[i][k] + graph[k][j] < graph[i][j]) {
						graph[i][j] = graph[i][k] + graph[k][j];
					}

		int min = 100000;
		for (int n = 0; n < person_number; n++) {
			int box = 0;
			for (int m = 0; m < person_number; m++) {
				if(n!=m)
				box += graph[n][m];
			}
			if (min > box)
				min = box;
		}
		printf("#%d %d\n",i+1, min);
	}

	return 0;
}