[백준] 1956 운동

문제링크: www.acmicpc.net/problem/1956

1956번: 운동

문제를 보자마자 플로이드 워셜로 모든 경로를 저장할 수 있다는 것을 알았다.

N이 400이기 때문이다.

정답을 제출한 다음 이것보다 더 빠른 속도를 보이는 풀이를 보니

배열을 초기화 할 때 Arrays.fill을 쓰는 것 같았다. 나도 넣어줬더니 제출결과가 30% 빠르게 나왔다.

import java.io.*;
import java.util.*;
public class Main {
	
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		int [][]dist = new int[V+1][V+1];
		for(int i=1;i<=V;i++)
			Arrays.fill(dist[i],987654321);
		for(int i=0;i<E;i++){
			st = new StringTokenizer(br.readLine());
			int a=  Integer.parseInt(st.nextToken());
			int  b = Integer.parseInt(st.nextToken());
			int c=  Integer.parseInt(st.nextToken());
			dist[a][b] = c;
		}
		
		for(int i=1;i<=V;i++){
			for(int j=1;j<=V;j++){
				for(int k=1;k<=V;k++){
					if(dist[i][k] + dist[k][j] < dist[i][j]){
						dist[i][j] = dist[i][k]+dist[k][j];
					}
				}
			}
		}
		int ans = 987654321;
		for(int i=1;i<=V;i++){
			ans = Math.min(ans, dist[i][i]);
		}
		if(ans < 987654321)
		System.out.println(ans);
		else System.out.println(-1);
	}

}