1238

[geonnho0]

문제 링크

[geonnho0]

각 마을에서 X번 마을까지 오고 가는 거리를 모두 구한 뒤, 해당 거리들의 최대값을 구하면 돼요.

거리는 최단 거리이기 때문에, 1번부터 N번까지 다익스트라를 통해 구할 수 있어요.

코드

public class Main {

    static int[][] distances;
    static ArrayList<Node>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());
        distances = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++)
                distances[i][j] = Integer.MAX_VALUE;
            distances[i][i] = 0;
        }
        graph = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) graph[i] = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            graph[start].add(new Node(end, weight));
        }
        for (int i = 1; i <= N; i++)
            dijkstra(i);
        int max = 0;
        for (int i = 1; i <= N; i++) {
            int temp = distances[i][X] + distances[X][i];
            max = Math.max(max, temp);
        }
        System.out.println(max);
    }

    static void dijkstra(int start) {
        distances[start][start] = 0;
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(start, 0));

        while (!queue.isEmpty()) {
            Node node = queue.poll();

            if (node.weight > distances[start][node.num])
                continue;

            for (Node n: graph[node.num]) {
                if (node.weight + n.weight >= distances[start][n.num])
                    continue;
                distances[start][n.num] = node.weight + n.weight;
                queue.offer(new Node(n.num, distances[start][n.num]));
            }
        }
    }

}

class Node implements Comparable<Node> {
    int num, weight;

    public Node(int num, int weight) {
        this.num = num;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return weight - o.weight;
    }
}