boj 1956: 운동

그래프에서 사이클의 길이 중 최소 길이를 찾는 문제이다.

d[i][i]를 무한대로 초기화해 준 뒤 플로이드 알고리즘을 적용하면 i->i로 가는 어떠한 경로 중 최소 길이를 얻을 수 있다.

 

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 m = in.nextInt();
		int mat[][] = new int[n + 1][n + 1];

		for (int i = 1; i <= n; i++) {
			Arrays.fill(mat[i], Integer.MAX_VALUE);
		}
		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int cost = in.nextInt();
			mat[start][end] = Math.min(mat[start][end], cost);
		}

		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (mat[i][k] != Integer.MAX_VALUE && mat[k][j] != Integer.MAX_VALUE) {
						mat[i][j] = Math.min(mat[i][j], mat[i][k] + mat[k][j]);
					}
				}
			}
		}

		int min = mat[1][1];
		for (int i = 2; i <= n; i++) {
			min = Math.min(min, mat[i][i]);
		}

		if (min == Integer.MAX_VALUE) {
			min = -1;
		}
		System.out.println(min);
	}
}