hotaruの蛍雪日記

競プロとゲームをしています

PG BATTLE2020 ましゅまろ 難易度5 辞書順最小最短経路

www.youtube.com

問題情報

PG BATTLE2020 ましゅまろの4問中最後の問題。

問題文は動画を参照。 ジャッジはPG BATTLE2020 ましゅまろ参加者以外は利用できない模様。

  • 問題名: 辞書順最小最短経路
  • 難易度: 5
  • 問題順: 4問中4問目の問題
  • コンテスト:PG BATTLE 2020 ましゅまろ

キーワード

幅優先探索(BFS)・最短経路・経路復元・辞書順最小

問題概要

N頂点M辺の有向グラフである部屋と通路がある。 部屋1から部屋Nまでの最短経路のうち辞書順最小のものを答えよ。 計算量はO(N\log_2N)以下か?。

考えること

すべての辺の長さが1のとき、最短経路は幅優先探索で見つけられる。

辞書順最小の経路を見つけたい。 辞書順が小さい部屋を優先してBFSすると最短かつ辞書順最小の経路が見つけられる。 なぜならで同じ部屋が2回探索されるとき、その探索している経路は最短経路もしくは辞書順最小ではないから。

経路復元は、どの部屋から移動して部屋に来たかを記録しておいて、その情報から復元する。

実装

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

// 入出力を除いて部屋番号と通路番号は0-basedとする
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    // 入力
    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
        a[i]--, b[i]--;  // 0-basedに変換
    }

    // graph[i]: 部屋iから通路を通って行ける部屋
    vector<set<int>> graph(n);
    for (int i = 0; i < m; i++) {
        graph[a[i]].insert(b[i]);
    }

    // prevnode[i]: 最短経路探索時に部屋iの前にいた部屋
    vector<int> prevnode(n, -1);
    prevnode[0] = 0;

    // 幅優先探索
    // 部屋0から部屋N-1までの最短経路を探索する
    // 経路を辞書順最小にするため、番号が小さい部屋を優先して探索する

    // 次に探索する部屋キュー
    queue<int> nextdest;
    nextdest.emplace(0);
    while (!nextdest.empty()) {
        const int p = nextdest.front();
        nextdest.pop();

        if (p == n - 1) break;

        // 部屋pから移動できる部屋 番号昇順
        for (auto &&np : graph[p]) {
            // npはもう探索した
            if (prevnode[np] >= 0) continue;
            prevnode[np] = p;

            nextdest.emplace(np);
        }
    }

    // 答え出力
    // prevnode[n - 1]が更新されていない=部屋N-1に到達できていない
    if (prevnode[n - 1] < 0) {
        cout << -1 << "\n";
        return 0;
    }

    deque<int> ans;

    // prevnodeから最短経路を復元
    int p = n - 1;
    while (p != 0) {
        ans.emplace_front(p);
        p = prevnode[p];
    }
    ans.emplace_front(0);

    // 配列ansをスペース区切りで出力
    for (auto i = ans.begin(); i != ans.end(); i++) {
        cout << *i + 1 << (i != ans.end() - 1 ? ' ' : '\n');
    }
}

感想

これ本番で解けない(考察ミス)ってマジすか? 経路復元はやったことがなかったのでそれは勉強になった。 経路復元はけんちょんのブログが詳しいです。