boj 1507: 궁금한 민호

플로이드 알고리즘의 결과가 주어졌을 때,

가능한 경우의 그래프의 최소 간선 수를 구하고, 모든 도로의 cost 합을 구하는 문제이다.

 

원래 플로이드 알고리즘은

• i->j로 가는 비용이 x보다 클 때, i->k->j로 가는 비용이 x이면 i->j로 가는 도로의 cost를 x로 바꿔준다

이 것을 반대로 적용해보면

• i->j로 가는 비용이 x일 때, i->k->j로 가는 비용이 x이면 i->j로 가는 도로는 필요없다.

입력이 이미 최단경로가 주어져있는데 다시 최단경로를 계산해보니 더 짧아진 경우는 입력이 모순이 되므로 -1을 출력하도록 했다.

 

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int mat[][] = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				mat[i][j] = in.nextInt();
			}
		}

		int ans = 0;
		boolean isEdge[][] = new boolean[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			Arrays.fill(isEdge[i], true);
		}

		Floyd: 
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				if (k == i) {
					continue;
				}
				for (int j = 1; j <= n; j++) {
					if (k == j || i == j) {
						continue;
					}

					if (mat[i][j] > mat[i][k] + mat[k][j]) {
						ans = -1;
						break Floyd;
					}

					if (mat[i][j] == mat[i][k] + mat[k][j]) {
						isEdge[i][j] = false;
						isEdge[j][i] = false;
					}
				}
			}
		}

		if (ans != -1) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (isEdge[i][j]) {
						ans += mat[i][j];
					}
				}
			}
			ans /= 2; // 양방향이므로 2로 나눠준다.
		}
		System.out.println(ans);
	}
}