[JAVA]백준 1956번 - 운동

1956번: 운동 (acmicpc.net)

1956번: 운동

플로이드 워샬?셜? 저번에 해서 안 하려 했는데

쪕..고냥 했슴니당..

package baekjoon;
import java.io.*;
import java.util.*;

public class b1956 {
	static final int INF = 987654321;
	static Queue <Integer> queue = new LinkedList<>();
	static boolean visited[];
	static int arr[][];
	static int v;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		v = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());
		
		arr = new int[v][v];
		visited = new boolean[v];
		for(int i = 0 ; i < v ; i++)
		{
			Arrays.fill(arr[i], INF);
		}
		for(int i = 0 ; i < v ; i++)
		{
			arr[i][i] = 0;
		}
		for(int i = 0 ; i < e ; i++)
		{
			st = new StringTokenizer(br.readLine());
			int row = Integer.parseInt(st.nextToken())-1;
			int col = Integer.parseInt(st.nextToken())-1;
			int cost = Integer.parseInt(st.nextToken());
			
			arr[row][col] = cost;
		}
		
		for(int i = 0 ; i < v ; i++)
		{
			for(int j = 0 ; j < v ; j++)
			{
				for(int k = 0 ; k < v 	; k++)
				{
					arr[j][k] = Math.min(arr[j][k], arr[j][i]+arr[i][k]);
				}
			}
		}

		int ans = INF;
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; j++) {
				if(i == j)
					continue;
                if (arr[i][j] != INF && arr[j][i] != INF) {
                    ans = Math.min(ans, arr[i][j] + arr[j][i]);
                }
            }
        }
        ans = ans == INF ? -1 : ans;
        
		bw.write(ans+"");
		bw.close();
		
	}
}

사이클 생기는 거를 어떻게 처리해야하나 고민하다가 첨에 bfs로 했는데 bfs로 하면 갈 수 있는 경로 쭉 다 세지니까 

(구글링) ij ji로 본인에게 가는 경우가 있나 저런식으로 했슴니다 어찌보면 당연한건데 ㅠㅡㅠ 반성하겠습니다 ㅠ

INF 충분히 키워야해요 저거때메 틀렸습니다 계속 뜸 ㅠㅠ