[백준(Baekjoon)][자바(java)] 1956 : 운동 / 최단 경로

 

www.acmicpc.net/problem/1956

1956번: 운동

 

문제 풀이

 

-   방향 그래프의 플로이드-워샬( floyd-warshall ) 알고리즘 응용 문제

-   인접 행렬로 그래프 표현

-   ( 배열의 0부터 사용하기 위해 정점 번호 입력받을 때 1씩 뺌 )

-   각 시작정점으로 되돌아오는 0보다 큰 경로가 존재할 때, 사이클이 있다고 판단.  그 중 최솟값을 구한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static final int max = 3990001;
	
	public static int floydWarshall_cycle( int d[][], int e[][], int n ) {
		int i, j, k, d_c_m = max, d_c;	// distance_cycle_min, distance_cycle
		for( i = 0; i < n; i++ ) 
			for( j = 0; j < n; j++ )
				if( i != j )
					d[i][j] = e[i][j] == 0 ? max : e[i][j];
		for( k = 0; k < n; k++ ) {
			for( i = 0; i < n; i++ ) {
				for( j = 0; j < n; j++ ) {
					if( i == j ) {
						if( d[i][k] != max && d[k][j] != max ) {
							d_c = d[i][k] + d[k][j];
							if( d_c_m > d_c && d_c > 0 )
								d_c_m = d_c;
						}
						continue;
					}
					if( d[i][j] > d[i][k] + d[k][j] )
						d[i][j] = d[i][k] + d[k][j];
				}
			}
		}
		return d_c_m == max ? -1 : d_c_m;
	}
	

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int V = Integer.parseInt( st.nextToken() ),
			E = Integer.parseInt( st.nextToken() ), a, b, c, i, dist;
		int d[][] = new int[V][V];
		int e[][] = new int[V][V];
		for( i = 0; i < E; i++ ) {
			st = new StringTokenizer( br.readLine() );
			a = Integer.parseInt( st.nextToken() ) - 1;
			b = Integer.parseInt( st.nextToken() ) - 1;
			c = Integer.parseInt( st.nextToken() );
			e[a][b] = c;
		}
		br.close();

		dist = floydWarshall_cycle( d, e, V );
	
		System.out.println( dist );
	}
}