백준 21940 java

문제 조건 중 이해하기 어려운 부분이 있었다.
정답 조건은 왕복시간들의 합 중 최소를 구하는게 아니라 왕복시간의 최대값중 최소를 구하는 것이다.

그런데 실행시간과 메모리 사용에서 다른 풀이보다 비효율이 컸다. Scanner를 써서 그런것도 있지만 다른 이유가 더 있는거 같다...

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.Vector;

public class bj21940 {
    static Scanner scanner = new Scanner(System.in);
    static int[][] city;
    static int[] location;

    public static void main(String[] args) {
        inputData();
        findAnswer();

        scanner.close();
    }

    public static void inputData() {
        System.out.println("\ninputData()");
        int N, M, K;
        int i;
        int A, B, T, C;

        N = scanner.nextInt();
        M = scanner.nextInt();
        city = new int[N + 1][N + 1];
        for(i = 1; i < city.length; i++)
        {
            Arrays.fill(city[i], 200000);
            city[i][i] = 0;
        }

        for (i = 0; i < M; i++) {
            A = scanner.nextInt();
            B = scanner.nextInt();
            T = scanner.nextInt();
            city[A][B] = T;//일방통행만 가능
        }

        K = scanner.nextInt();
        location = new int[K];
        for (i = 0; i < location.length; i++) {
            C = scanner.nextInt();
            location[i] = C;
        }
    }

    public static void findAnswer() {
        System.out.println("\nfindAnswer()");
        int maxTime = Integer.MAX_VALUE;
        int current = 0;
        int selectedCity;
        int i;
        Vector<Integer> whichCityIsTheBestOption = new Vector<>();

        //도시 X까지 왕복하는데 걸리는 시간들 중 최댓값을 구하고
        //그 최댓값들 중 최솟값인 도시 X들을 찾으라

        floydWarshall();//플로이드 워셜 수행

        for(i = 1; i < city.length; i++)
        {
            selectedCity = i;
            current = 0;
            for(int cityNum : location)
            {
                current = Math.max(current, city[cityNum][selectedCity] + city[selectedCity][cityNum]);
                System.out.println(cityNum +"에서 " + selectedCity + "으로 왕복하는 current : " + current);
            }
            System.out.print("선택된 도시 번호 " + selectedCity);
            System.out.println(" 에서 왕복 최대값 current " + current);

            if(current < maxTime)//새로운 최소 시간으로 갱신
            {
                System.out.println("기존 최대값 갱신!");
                maxTime = current;
                whichCityIsTheBestOption.clear();//기존 벡터 초기화
                whichCityIsTheBestOption.add(selectedCity);
            }
            else if(current == maxTime)
            {
                whichCityIsTheBestOption.add(selectedCity);
            }
        }

        Collections.sort(whichCityIsTheBestOption);
        for(int cityNum : whichCityIsTheBestOption)
        {
            System.out.print(cityNum + " ");
        }
        System.out.println();
    }

    public static void floydWarshall() {
        System.out.println("\nfloydWarshall()");
        int i, j, k;
        int N = city.length;

        for(k = 1; k < N; k++)
        {
            for(i = 1; i < N; i++)
            {
                for(j = 1; j < N; j++)
                {
                    city[i][j] = Math.min(city[i][j], city[i][k] + city[k][j]);
                }
            }
        }

        System.out.println("플로이드 워셜 결과");
        for(i = 1; i < N; i++)
        {
            for(j = 1; j < N; j++)
            {
                System.out.print(city[i][j] + " ");
            }
            System.out.println();
        }
    }
}