[白俊]#11779最低料金取得2

質問する

n(1≦n≦1000)都市がある.ある都市から別の都市へのm(1≦m≦100000)シャトルバスもあります.私たちはAからBまでのバスの料金を最小限に抑えたいです.それではAからBまでの最小費用とルートを印刷します.始点から終点までのパスは常に存在します.

入力

1行目は都市の個数n(1≦n≦1000)を与え、2行目はバスの個数m(1≦m≦100000)を与える.次に、3行目からm+2行目まで、次のバスの情報を与えます.まず、最初にそのバスの出発都市番号をあげます.そして到着地のシティナンバー、そしてバス代です.バス料金は0以上、100000未満の整数です.
次に、m+3行は、私たちが要求した区間の起点の都市番号と到着点の都市番号を与えます.

しゅつりょく

最初の行は、出発都市から到着都市までの最小費用を出力します.
2行目の出力は、最低コストのパスに含まれる都市の数です.出発都市と到着都市も含まれています.
3行目は、アクセスコストが最も低いパスを都市順に出力します.

入力例1

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

サンプル出力1

4
3
1 3 5

に答える

この問題はDijkstraアルゴリズムで解くことができる.多翼点アルゴリズムはQueueを用いて実現し,経路はbacktrackingを用いて解いた.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int N;
    static ArrayList<Pair>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        graph = new ArrayList[N+1];

        for(int i=1; i<=N; i++)
            graph[i] = new ArrayList<>();

        for(int i=0; i<M; i++) {
            String[] input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0]);
            int end = Integer.parseInt(input[1]);
            int cost = Integer.parseInt(input[2]);

            graph[start].add(new Pair(end, cost));
        }

        String[] input = br.readLine().split(" ");
        int start = Integer.parseInt(input[0]);
        int end = Integer.parseInt(input[1]);

        dijkstra(start, end);
    }

    public static void dijkstra(int start, int end) {
        Queue<Pair> queue = new LinkedList<>();
        int[] distance = new int[N+1];
        for(int i=0; i<=N; i++)
            distance[i] = Integer.MAX_VALUE;

        distance[start] = 0;
        int[] path = new int[N+1];
        queue.add(new Pair(start, 0));

        while(!queue.isEmpty()) {
            Pair temp = queue.poll();
            
            if(distance[temp.end] < temp.cost) continue;

            for(int i=0; i<graph[temp.end].size(); i++) {
                Pair p = graph[temp.end].get(i);

                if(distance[p.end]>p.cost+temp.cost) {
                    queue.add(new Pair(p.end, temp.cost+p.cost));
                    distance[p.end] = temp.cost+p.cost;
                    path[p.end] = temp.end;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        int cnt = 1;
        int idx = end;
        sb.append(end);
        while(path[idx]!=0) {
            sb.insert(0, path[idx]+" ");
            idx = path[idx];
            cnt++;
        }
        sb.insert(0, cnt+"\n");
        sb.insert(0, distance[end]+"\n");
        System.out.println(sb.toString());
    }

    public static class Pair {
        int end;
        int cost;

        public Pair(int end, int cost) {
            this.end = end;
            this.cost = cost;
        }
    }
}