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

23679 ワード
白駿 金貨 アルゴリズム#アルゴリズム# テキストリンク
問題のショートカット
私の答え
平凡な多芸の星で解けた.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));
                }
            }
        }
    }
}
パフォーマンスのチューニング:ViewPagerの高速切り替え時のカートンのソリューション-Fragmentコンテンツの遅延ロード
私の学習:API 101＆郵便配達人