[swexpert] 1263. 사람 네트워크2 (java, 플로이드 와샬)

나는 연결이 안된 사람을 -1로 써줬다. 

 

플로이드 와샬 알고리즘을 볼 때 s(시작점) 중간노드 (k) e(끝 점) 의 거리를 업데이트 해줄 때

중간에 연결이 안된 사람이거나 (dist[s][k]==-1 || dist[k][e]==-1) 

두 지점은 연결되어 있고 dist[s][e]가 연결이 안되어있는 상태인 경우 dist[s][e]==-1 dist[s][e]=dist[s][k]+dist[k][e]로

업데이트를 해줬다.

 

import java.util.Scanner;

public class Solution {
	static int t,n;
	static int[][] dist;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		t=sc.nextInt();
		for (int tc = 1; tc <=t; tc++) {
			n=sc.nextInt();
			dist=new int[n][n];// 거리를 저장한다.
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					dist[i][j]=sc.nextInt();
					if(i!=j && dist[i][j]==0) {
						dist[i][j]=-1;
					}
				}
			}

			floyd();

			int min_sum=Integer.MAX_VALUE;
			int answer=1;
			for (int i = 0; i < n; i++) {
				int temp=0;
				for (int j = 0; j < n; j++) {
					if(dist[i][j]==-1)continue;
					temp+=dist[i][j];
				}
				if(temp<min_sum) {
					min_sum=temp;
					answer=i+1;
				}
			}
			System.out.printf("#%d %d\n",tc,min_sum);
		}

	}
	private static void floyd() {
		for (int k = 0; k < n; k++) {
			for (int s = 0; s < n; s++) {
				if(k==s)continue;
				for (int e = 0; e < n; e++) {
					if(s==e || k==e)continue; // 같은 정점은 pass한다.
					if(dist[s][k]==-1 || dist[k][e]==-1)continue;
					if(dist[s][e]==-1 || dist[s][k]+dist[k][e]<dist[s][e]) {
						dist[s][e]=dist[s][k]+dist[k][e];
					}
				}
			}
		}
		
	}

}