標準理想パス(3526)

理想の道

1.ヒント

1)一番前の経路をアルファベット順で検索するには、111号室から常に最小の幹線をアルファベット順で使用してください。

2)同時に最短経路でなければならないため最短経路に属する頂点にしか移動できず、NNN号頂点が逆BFSでdist配列が完了した後、dist[here]-1=dist[there]であればthereが最短経路が通る頂点であることが分かる。

3）BFSを介して理想経路を逆方向に追跡する過程で、幹線を検査し、最小重みの幹線をすべてQueueに入れる。これらの幹線は複数あります。

2.近接

1)最短パス

(1,N)(1,N)(1,N)(1,N)(1,N)(1,N)の最短経路長は幹線の重み付け値を無視してBFSにより簡単に求めることができる.しかし,最短経路であると同時に辞書順で上位に並ぶ経路をどのように見つけるか.最短パスを考慮しない場合は、辞書順に並べられた最短パスを使用するだけで、辞書順に最短パスを検索できます.しかし、これは最短経路ではありません.

2）リバーストレース

6 5
1 2 7
2 4 8
1 3 8
3 5 9
5 6 10
=>
3
8 9 10

赤は111番の頂点から始まるBFSのdist配列、青は幹線の重み付け値を表します.理想的なパスを見つけるには、最短パスに属し、アルファベット順に一番前のパスに移動するしかありません.最短経路が通過する頂点であるか否かを容易に知る方法がある.

NNN番号の頂点でBFSを起動してdist配列を作成します.dist[here]-1=dist[there]がthere頂点に移動すると、常に最短パスであることが保証されます.ただし、最短パスが複数ある場合は、これらのパスをすべて移動する必要があります.だから辞書の順番で一番前のパスは111222...順にBFSを使用してリバーストレースを行います.

3.実施

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

    static void bfs(StringBuilder bw) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(N);
        dist = new int[N + 1];
        Arrays.fill(dist, -1);
        dist[N] = 0;
        while (!q.isEmpty()) {
            int here = q.poll();
            for (Pair p : adj.get(here)) if (dist[p.index] == -1) {
                int there = p.index;
                q.offer(there);
                dist[there] = dist[here] + 1;
            }
        }
        bw.append(dist[1]).append("\n");
    }

    static void construct(StringBuilder bw) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        boolean[] booked = new boolean[N + 1];
        booked[1] = true;
        while (!q.isEmpty()) {
            int size = q.size();
            // 사전순으로 가장 작은 가중치를 구한다
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < size; i++) {
                int here = q.poll();
                for (Pair p : adj.get(here)) {
                    int there = p.index;
                    if (dist[here] - 1 == dist[there]) {
                        min = Math.min(min, p.value);
                    }
                }
                q.offer(here);
            }
            if (min != Integer.MAX_VALUE) bw.append(min).append(" ");
            // 사전순으로 가장 작은 가중치를 갖는 간선이 여러개라면 모두 방문
            for (int i = 0; i < size; i++) {
                int here = q.poll();
                for (Pair p : adj.get(here)) {
                    int there = p.index;
                    if (p.value == min && !booked[there] &&
                    dist[here] - 1 == dist[there]) {
                        q.offer(there);
                        booked[there] = true;
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder bw = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        adj = new ArrayList<>();
        for (int i = 0; i <= N; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            adj.get(a).add(new Pair(b, c));
            adj.get(b).add(new Pair(a, c));
        }
        for (int i = 0; i <= N; i++) Collections.sort(adj.get(i));
        bfs(bw);
        construct(bw);
        System.out.println(bw);
    }

}
class Pair implements Comparable<Pair> {
    int index, value;

    Pair(int i, int v) { index = i; value = v; }

    @Override
    public int compareTo(Pair o) { return value - o.value; }
}

1）時間複雑度

全ての頂点はQueueに一度しか入らないので,O(V＋E)O(V＋E)O(V＋E)O(V＋E)はBFSと同じである.

2）テストケース

6 5
1 2 7
2 4 8
1 3 8
3 5 9
5 6 10
=>
3
8 9 10