[伯俊]1753号最短経路JAVA解答

問題のショートカット
私の答え
平凡な多芸の星で解けた.Pythonを使用している場合に比べて実装は確かに複雑になっているので正解ですが、時間も1000ミリ秒近く、メモリも100 MBに近いので、より効率的な解法を考えてみました.
500~600 msの時間で他の人がjavaでこの問題を解決したのを見ました...基本的なprintln()から,多様な方法を重畳し,最大限に短縮する.実際のエンタープライズクラスcoteでは,アルゴリズムの観点から効率を向上させることでjavaのライブラリ自体を修正して効率を向上させる問題は二度と現れないようであり,これ以上探していない.
結論:ダエストラも長い時間がかかります.
優先キューを使用するマルチタスク時間の複雑さはO(EGV)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

class Node implements Comparable<Node> {

    public int index;
    public int distance;

    public Node(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }

    @Override
    public int compareTo(Node o) {
        if (this.distance < o.distance) {
            return -1;
        }
        return 1;
    }
}

class Main {

    static final int INF = Integer.MAX_VALUE;
    static int v, e, k;
    static List<List<Node>> graph = new ArrayList<>();
    static int[] d = new int[20001];

    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());

        st = new StringTokenizer(br.readLine());
        k = Integer.parseInt(st.nextToken());

        for (int i = 0; i < v + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int i1 = Integer.parseInt(st.nextToken());
            int i2 = Integer.parseInt(st.nextToken());
            int i3 = Integer.parseInt(st.nextToken());
            graph.get(i1).add(new Node(i2, i3));
        }

        Arrays.fill(d, INF);

        dijkstra(k);
        for (int i = 1; i <= v; i++) {
            if (d[i] == Integer.MAX_VALUE) {
                System.out.println("INF");
            } else {
                System.out.println(d[i]);
            }
        }
    }

    public static void dijkstra(int start) {
        Queue<Node> q = new PriorityQueue<>();
        q.offer(new Node(start, 0));
        d[start] = 0;
        while (!q.isEmpty()) {
            Node node = q.poll();
            int dist = node.distance;
            int now = node.index;
            if (d[now] < dist) continue;
            for (int i = 0; i < graph.get(now).size(); i++) {
                int cost = d[now] + graph.get(now).get(i).distance;
                if (cost < d[graph.get(now).get(i).index]) {
                    d[graph.get(now).get(i).index] = cost;
                    q.offer(new Node(graph.get(now).get(i).index, cost));
                }
            }
        }
    }
}