문제

아이디어

최단 경로를 요구하는 그래프 탐색 문제이다.
다만 노드의 개수가 최대 400개 이하로 매우 적으니 플로이드-워셜 알고리즘을 이용해 풀이할 수 있다.
플로이드-워셜 알고리즘을 이용해 각 노드 사이의 최단경로를 구해주고 왕복 거리를 구해준다.
이 때 왕복 거리는 마을 A에서 마을 B로 향하는 도로의 길이를 R1, 마을 B에서 마을 A로 향하는 도로의 길이가 R2일 때 R1 + R2이다.

소스코드

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

public class Main {
    static int V, E;
    static int ans = Integer.MAX_VALUE;
    static int[][] road;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        road = new int[V + 1][V + 1];
        for (int i = 1; i <= V; i++) {
            Arrays.fill(road[i], Integer.MAX_VALUE);
        }

        int from, to, weight;
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());

            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            weight = Integer.parseInt(st.nextToken());

            road[from][to] = weight;
        }


        for (int k = 1; k <= V; k++) {
            for (int i = 1; i <= V; i++) {
                if (road[i][k] == Integer.MAX_VALUE) continue;
                for (int j = 1; j <= V; j++) {
                    if (road[k][j] == Integer.MAX_VALUE) continue;
                    road[i][j] = Math.min(road[i][j], road[i][k] + road[k][j]);
                }
            }
        }

        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                if (road[i][j] == Integer.MAX_VALUE || road[j][i] == Integer.MAX_VALUE) continue;
                ans = Math.min(ans, road[i][j] + road[j][i]);
            }
        }

        if (ans == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(ans);
    }
}

채점결과

두 실패 모두 63%에서 오답이었다.
testcase.ac에서 확인한 결과 도로가 존재하지 않을 때 오작동하였다.