[JAVA]백준_1956_운동

문제링크

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

1956번: 운동

 

사이클을 이룬다는 것이 무슨 의미인지 이해가 안가서 힘들었다.

아래의 질문 링크 두개를 참고하여 해결했다.

www.acmicpc.net/board/view/50597

글 읽기 - 플루이드 와샬 질문드림용

www.acmicpc.net/board/view/41881

글 읽기 - 사이클을 이루는지 알아볼때 질문있습니다!

package BOJ;

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

public class Main_1956 {
    static int INF = 999999999;
    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());
        int E = Integer.parseInt(st.nextToken());

        int map[][] = new int[V+1][V+1];
        for(int i=0;i<=V;i++){
            for(int j=0;j<=V;j++){
                map[i][j] = INF;
            }
        }

        for(int e=0;e<E;e++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            map[a][b] = c; //일반통행도로
            //도로의 길이의 합이 가장 작은 사이클 // 두 마을 왕복하는 경우도 사이클에 포함됨
        }
//        for(int i=0;i<=V;i++) System.out.println(Arrays.toString(map[i]));

        for(int k=1;k<=V;k++){
            for(int i=1;i<=V;i++){
                for(int j=1;j<=V;j++){
                    map[i][j] = Math.min(map[i][j],map[i][k]+map[k][j]);
                }
            }//map[i][j]까지 가는 최소 거리
        }//출-경-도로 가는 경우


//        for(int k=1;k<=V;k++){
//            for(int j=1;j<=V;j++){
//                for(int i=1;i<=V;i++){
//                    map[i][j] = Math.min(map[i][j],map[i][k]+map[k][j]);
//                }
//            }
//        }//출-경-도로 가는 경우
//
//        System.out.println("++++++++++++++++++++++++++++++++++");
//        for(int i=0;i<=V;i++) System.out.println(Arrays.toString(map[i]));

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

        System.out.println(min == Integer.MAX_VALUE?-1:min);
    }
}