Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

25. 최단 경로

그래프의 간선에 가중치가 없으면 BFS로 최단거리를 찾을 수 있습니다. 가중치가 있다면 어떨까요?

Java / Python

7. 운동

1956번

최단 거리 알고리즘을 응용하여 최단 사이클을 찾는 문제

이번 문제는 도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하는 문제입니다. (두 마을을 왕복하는 경우도 사이클에 포함됨에 주의해야 합니다.)
플로이드 와샬 알고리즘을 이용해서 모든 정점 사이의 최단경로를 구하는 방식입니다.

• Java

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

public class Main {        
	static int[][] dist; 
	static int V, E; // V개 마을, E개 도로
	static final int INF = 10000 * 400;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   
		StringTokenizer st = new StringTokenizer(br.readLine());
        
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken()); 
        
		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;
			}
		}
       
		while(E-- > 0) {
			st = new StringTokenizer(br.readLine());

			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			dist[start][end] = cost;
		}
        
		bw.write(floyd() + "\n");
        
		bw.flush();
		br.close();
		bw.close();
	}

	public static int floyd() { 
		for (int k = 1; k <= V; k++) {
			for (int i = 1; i <= V; i++) {
				for (int j = 1; j <= V; j++) {
					dist[i][j] = Math.min(dist[i][k] + dist[k][j], dist[i][j]);
				}
			}
		}
		int min = INF;
		for(int i = 1; i<=V; i++){
			min = Math.min(dist[i][i], min);
		}
		return min >= INF ? -1 : min;
	}
}

• Python

시간 초과 때문에 PyPy3로 제출했습니다..ㅠ

import sys
v, e = map(int, sys.stdin.readline().split())
inf = 100000000
dist = [[inf] * v for i in range(v)]
for i in range(e):
    a, b, c = map(int, sys.stdin.readline().split())
    dist[a - 1][b - 1] = c
for k in range(v):
    for i in range(v):
        for j in range(v):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
result = inf
for i in range(v):
    result = min(result, dist[i][i])
if result == inf:
    print(-1)
else:
    print(result)