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

연결 정보를 바탕으로 각 지점간 최단 거리 구하는 알고리즘에는

다익스트라도 있지만 플로이드 워셜 알고리즘도 존재한다.

3중 for문을 통해 arr[i][j] > arr[i][k] + arr[k][j]를 구현하는 것이고,

주의할 점은 자기 자신의 정점까지의 거리는 0 , 이어지지 않은 정점은 충분히 큰 수 10000정도를 입력하는 것이 중요. 

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;

int N, ans;
int arr[1001][1001];
int sum[1001];

int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{

		cin >> N;
		

		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				cin >> arr[i][j];
				if (!arr[i][j])
				{
					arr[i][j] = 10000;
				}
				if (i == j)
				{
					arr[i][j] = 0;
				}
			}
		}

		for (int k = 1; k <= N; k++)
		{
			for (int i = 1; i <= N; i++)
			{
				for (int j = 1; j <= N; j++)
				{
					if (arr[i][j] > arr[i][k] + arr[k][j])
					{
						arr[i][j] = arr[i][k] + arr[k][j];
					}
				}
			}
		}
		ans = 987654321;
		for (int i = 1; i <= N; i++)
		{
			int buf = 0;
			for (int j = 1; j <= N; j++)
			{
				buf += arr[i][j];
			}
			if (ans > buf)
			{
				ans = buf;
			}

		}
		
		cout << "#" << test_case << " " << ans << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}