접근 방법 ?

• 최단 사이클 경로를 구하면 된다,

• 다익스트라를 이용해서 최단 거리를 구할 때, 출발점에 대한 거리를 0이 아닌 최댓값으로 초기화해서, 출발점까지 도달할 수 있도록 구현

• 플로이드 워셜 알고리즘을 이용해서도 해결 가능

다익스트라 ?

• 다익스트라는 우선순위큐를 이용해서 구현

• 거리에 대한 배열을 선언해, 우선순위큐의 아이템이 구해진 거리보다 크다면 드랍시키도록 구현, 등호를 쓰지 않도록 주의

• 시간복잡도는 O(ElogE)이 발생

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		List<Integer>[] list;
		int[][] cost;
		int answer = Integer.MAX_VALUE;
		
		int V = Integer.parseInt(stk.nextToken());
		int E = Integer.parseInt(stk.nextToken());
		cost = new int[V + 1][V + 1];
		list = new List[V + 1];
		
		for(int i = 1; i <= V; i++){
			list[i] = new ArrayList<>();
		}
		
		for(int i = 0; i < E; i++){
			stk = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(stk.nextToken());
			int b = Integer.parseInt(stk.nextToken());
			int c = Integer.parseInt(stk.nextToken());
			
			list[a].add(b);
			cost[a][b] = c;
		}
		
		for(int i = 1; i <= V; i++){
			PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (a[1] - b[1]));
			pq.add(new int[]{i, 0});
			
			int[] dist = new int[V + 1];
			for(int j = 1; j <= V; j++) dist[j] = Integer.MAX_VALUE;
			int result = Integer.MAX_VALUE;
			
			while(!pq.isEmpty()){
				int[] e = pq.poll();
				if(dist[e[0]] < e[1]) continue;
				
				for(int next : list[e[0]]){
					if(dist[next] > e[1] + cost[e[0]][next]){
						dist[next] = e[1] + cost[e[0]][next];
						pq.add(new int[]{next, dist[next]});
					}
				}
			}
			
			answer = Math.min(answer, dist[i]);
		}
			
		if(answer == Integer.MAX_VALUE)
			bw.write("-1\n");
		else
			bw.write(answer + "\n");
			
		bw.flush();
	}
}

플로이드 워셜 ?

• 자기 자신에 대한 거리는 최댓값으로 초기화

• 시간복잡도는 O(V^3)

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		List<Integer>[] list;
		int[][] cost;
		int[][] dist;
		int answer = Integer.MAX_VALUE;
		
		int V = Integer.parseInt(stk.nextToken());
		int E = Integer.parseInt(stk.nextToken());
		cost = new int[V + 1][V + 1];
		dist = new int[V + 1][V + 1];
		list = new List[V + 1];
		
		for(int i = 1; i <= V; i++){
			list[i] = new ArrayList<>();
		}
		
		for(int i = 1; i <= V; i++){
			for(int j = 1; j <= V; j++){
				dist[i][j] = Integer.MAX_VALUE;
			}
		}
		
		for(int i = 0; i < E; i++){
			stk = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(stk.nextToken());
			int b = Integer.parseInt(stk.nextToken());
			int c = Integer.parseInt(stk.nextToken());
			
			list[a].add(b);
			cost[a][b] = c;
			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[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE){
						dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
					}
				}
			}
		}
		
		for(int i = 1; i <= V; i++)
			answer = Math.min(answer, dist[i][i]);
			
		if(answer == Integer.MAX_VALUE)
			bw.write("-1\n");
		else
			bw.write(answer + "\n");
			
		bw.flush();
	}
}