백준 1956- 운동 (java)

https://www.acmicpc.net/problem/1956

각 모든 정점에서 각 모든 정점까지의 최단거리를 구할 수 있는 플로이드 워셜 알고리즘을 사용하여 푸는 문제이다.

그래프에 음수사이클만 존재하지 않으면 다익스트라와 다르게 음수인 간선이 있어도 상관없다.

3중 for문을 돌며 어디를 거치지 않고 직행하는 거리가 짧은지, 경유해서 가는 거리가 짧은지 비교해 갱신하는 방법이다.

public class Main {  
  
	public static void main(String[] args) throws Exception {  
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
		StringTokenizer st;  
		StringBuilder sb = new StringBuilder();  
  
		st = new StringTokenizer(br.readLine());  
  
		final int INF = 987654321;  
		int V = Integer.parseInt(st.nextToken());  
		int E = Integer.parseInt(st.nextToken());  
  
		int[][] arr = new int[V+1][V+1];  
  
		for(int i = 1; i < V+1; i++){  
			for(int j = 1; j < V+1; j++){  
				if(i == j) arr[i][j] = 0;  
				else arr[i][j] = INF;  
			}  
		}  
  
		for(int i = 0; i < E; i++){  
			st = new StringTokenizer(br.readLine());  
  
			int u = Integer.parseInt(st.nextToken());  
			int v = Integer.parseInt(st.nextToken());  
			int w = Integer.parseInt(st.nextToken());  
  
			arr[u][v] = w;  
		}  
  
		for(int k = 1; k < V+1; k++){//경유지  
			for(int i = 1; i < V+1; i++){//출발지  
				for(int j = 1; j < V+1; j++){//도착지  
					if(arr[i][j] > arr[i][k] + arr[k][j]){  
						arr[i][j] = arr[i][k] + arr[k][j];  
					}  
				}  
			}  
		}  
  
		int min = Integer.MAX_VALUE;  
		for(int i = 1; i < V+1; i++){  
			for(int j = 1; j < V+1; j++){  
				if(i == j) continue;  
				if(arr[i][j] != INF && arr[j][i] != INF){  
					min = Math.min(min, arr[i][j] + arr[j][i]);  
				}  
			}  
		}  
  
		if(min == Integer.MAX_VALUE) min = -1;  
			System.out.print(min);  
		}  
}