문제 - 운동

문제접근

처음에는 dfs로 이용해서 사이클을 찾으려고 했지만 두 마을만 거쳐도 사이클을 어떻게 찾아야할지 조건을 찾지 못해서 다른 알고리즘을 생각하게 되었다.
1. 모든 정점에서 모든 정점까지의 최소 거리를 구한다. -> 플로이드와샬 알고리즘을 사용 다익스트라를 사용해도된다. 하지만 V가 500이상이 아니여서 O(V^3)을 해도 시간초과가 나지 않는다.
2. 사이클을 찾아서 최소 거리를 구한다.

플로이드 와샬

		//거쳐야되는 중간 지점
        for(int k=1;k<=v;k++)
        {
            //시작지점
            for(int i=1;i<=v;i++)
            {
                if(i==k) continue;
                //종착지점
                for(int j=1;j<=v;j++)
                {
                    if(j == k || j == i) continue;
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

소스코드

import java.util.*;
/*
3 4
1 2 1
3 2 1
1 3 5
2 3 2
 */
public class Main {
    static int INF =400*10_000*2;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int v = sc.nextInt();
        int e = sc.nextInt();
        int ans = INF;

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

        for(int i=1;i<=v;i++) {
            for (int j = 1; j <= v; j++)
            {
                dist[i][j] = INF;
            }
        }

        for(int i=0;i<e;i++)
        {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();

            dist[a][b] = c;
        }

        //플로이드 와샬
        //거쳐야되는 중간 지점
        for(int k=1;k<=v;k++)
        {
            //시작지점
            for(int i=1;i<=v;i++)
            {
                if(i==k) continue;
                //종착지점
                for(int j=1;j<=v;j++)
                {
                    if(j == k || j == i) continue;
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        //사이클 찾기
        for(int i=1;i<=v;i++)
        {
            for(int j=1;j<=v;j++)
            {
                if(i==j) continue;
                else {
                    if(dist[i][j] != INF && dist[j][i] != INF)
                        ans = Math.min(ans, dist[i][j] + dist[j][i]);
                }
            }
        }

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


}