結果

問題 No.160 最短経路のうち辞書順最小
ユーザー ぴろず
提出日時 2015-02-26 02:16:06
言語 Java
(openjdk 23)
結果
AC  
実行時間 523 ms / 5,000 ms
コード長 2,908 bytes
コンパイル時間 3,189 ms
コンパイル使用メモリ 82,204 KB
実行使用メモリ 59,592 KB
最終ジャッジ日時 2024-06-23 23:37:32
合計ジャッジ時間 11,289 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package graph.ans1;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int s = sc.nextInt();
        int g = sc.nextInt();
        int[] a = new int[m];
        int[] b = new int[m];
        int[] c = new int[m];
        for(int i=0;i<m;i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
            c[i] = sc.nextInt();
        }
        ArrayList<Integer> ans = solve(n, m, s, g, a, b, c);
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<ans.size();i++) {
            if (i > 0) {
                sb.append(' ');
            }
            sb.append(ans.get(i));
        }
        System.out.println(sb.toString());
    }
    public static ArrayList<Integer> solve(int n,int m,int start,int goal,int[] a,int[] b,int[] c) {
        Graph g = new Graph(n);
        for(int i=0;i<m;i++) {
            g.addBidirectionalEdge(a[i], b[i], c[i]); //無向辺の追加(有向辺を2つ張る)
        }
        int[] dist = g.minDistDijkstra(goal); //ゴールからダイクストラ
        //辞書順最小になるように、経路復元しながら貪欲的に選ぶ
        //無向辺なので実装は簡単
        ArrayList<Integer> ans = new ArrayList<>();
        int now = start;
        ans.add(now);
        while(true) {
            int next = 1 << 29;
            for(Graph.Edge e:g.graph[now]) { //nowから出てる辺全てに対して処理
                if (dist[now] == dist[e.to] + e.cost) {
                    next = Math.min(next, e.to);
                }
            }
            now = next;
            ans.add(now);
            if (now == goal) {
                break;
            }
        }
        return ans;
    }
}
class Graph {
    public static final int INF = 1<<29;
    int n;
    ArrayList<Edge>[] graph;
    @SuppressWarnings("unchecked")
    public Graph(int n) {
        this.n = n;
        this.graph = new ArrayList[n];
        for(int i=0;i<n;i++) {
            graph[i] = new ArrayList<Edge>();
        }
    }
    public void addBidirectionalEdge(int from,int to,int cost) {
        addEdge(from,to,cost);
        addEdge(to,from,cost);
    }
    public void addEdge(int from,int to,int cost) {
        graph[from].add(new Edge(to, cost));
    }
    //dijkstra O(ElogV)
    public int[] minDistDijkstra(int s) {
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[s] = 0;
        PriorityQueue<Node> q = new PriorityQueue<Node>();
        q.offer(new Node(0, s));
        while(!q.isEmpty()) {
            Node node = q.poll();
            int v = node.id;
            if (dist[v] < node.dist) {
                continue;
            }
            for(Edge e:graph[v]) {
                if (dist[e.to] > dist[v] + e.cost) {
                    dist[e.to] = dist[v] + e.cost;
                    q.add(new Node(dist[e.to], e.to));
                }
            }
        }
        return dist;
    }
    class Edge {
        int to;
        int cost;
        public Edge(int to,int cost) {
            this.to = to;
            this.cost = cost;
        }
    }
    class Node implements Comparable<Node>{
        int dist;
        int id;
        public Node(int dist,int i) {
            this.dist = dist;
            this.id = i;
        }
        public int compareTo(Node o) {
            return (this.dist < o.dist) ? -1 : ((this.dist == o.dist) ? 0 : 1);
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0