운동 1956

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

플로이드 워샬이 3중 for문이구나...

두 지점간의 가장 짧은 거리를 구하는 것이다.

이 문제같은 경우 자기자신으로 사이클이 생길 수도 있는 예외가 있다

바깥쪽 for문이 중간경로
중간쪽 for문이 시작
안쪽 for문이 도착 지점의 인덱스로 생각하고 짜야한다

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");

        int v = Integer.parseInt(input[0]);
        int e = Integer.parseInt(input[1]);

        int[][] dist = new int[v+1][v+1];
        int INF = 10000000;

        for (int i = 1; i <= v; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }

        for (int i = 0; i < e; i++) {
            input = br.readLine().split(" ");

            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            int c = Integer.parseInt(input[2]);

            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[j][k] > dist[j][i] + dist[i][k])
                        dist[j][k] = dist[j][i] + dist[i][k];
                }
            }
        }

        int result = INF;
        for (int i = 1; i <= v; i++)
            for (int j = 1; j <= v; j++){
                if(i == j && dist[i][j] == 0)
                    continue;

                if (dist[i][j] != INF && dist[j][i] != INF){
                    if(i == j){
                        result = Math.min(result, dist[i][j]);
                    }else
                        result = Math.min(result, dist[i][j] + dist[j][i]);
                }

            }


        if (result == INF) System.out.println(-1);
        else System.out.println(result);
    }
}