[백준] 1956: 운동 - JAVA

in Algorithm on 그래프 이론

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

풀이

v개의 정점과 e개의 간선이 주어진다.

출발점에서 다시 출발점으로 돌아오는 사이클이 있는지, 있다면 최솟값을 구하는 문제이다.

모든 정점에서 다른 모든 정점까지의 최단경로가 필요하다. -> 플로이드 워셜 알고리즘을 사용한다.

원래 알고있던 플로이드 워셜에서는 거리를 저장할 이차원배열을 만들고, 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화를 했었다.

하지만 이 문제에서는 자기 자신에서 자기 자신으로 돌아와야하므로 다른 값들과 마찬가지로 INF로 초기화하였다.

그리고나서 플로이드 워셜 알고리즘을 통해 i정점에서 k를 거쳐 j로 이동하는 최솟값을 갱신해주면 자기 자신으로 다시 돌아오는 거리도 갱신된다.

dist[i][i] 중 최솟값을 출력하면 된다.

메모리: 67480KB

시간: 696ms

언어: Java 11

코드

import java.util.*;
import java.io.*;

public class Main {
    static final int INF = 1_000_000_000;

    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 + 1; i++) {
            for (int j = 1; j < v + 1; j++) {
                dist[i][j] = INF;
            }
        }

        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 k = 1; k < v + 1; k++) {
            for (int i = 1; i < v + 1; i++) {
                for (int j = 1; j < v + 1; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        int ans = INF;
        for (int i = 1; i < v + 1; i++) {
            ans = Math.min(ans, dist[i][i]);
        }

        System.out.println(ans == INF ? -1 : ans);
    }

}