ARC056 B - 駐車場

問題

N 人の人が 1 番目から順に駐車場にやってくる。駐車場は N 個の駐車スペースが無向辺で結ばれたグラフで表され、入り口は頂点 S である。i 番目の人は i 番目の駐車スペースに車を停めるか、停められないならば停めずに帰る。

駐車できる人の番号をすべて出力せよ。

制約

1 <= N, M <= 2 * 10 ^ 5

グラフは連結

解法

i 番目の人が i 番目のスペースに駐車できることは、S から頂点 i に至る、 i 以上の頂点からなる経路が存在することと同値である。つまり目的地までできるだけ番号の大きい頂点を通っていきたいので、これを表現するコストを定義し"最短路問題"のようなものを考える。

コストは d_i = (頂点 i にたどり着くために経由しなければならない頂点の最小の番号の最大値) とすればよい。普通の dijkstra ではコストの小さい頂点から確定していくが、今回はコストが大きい方がいいので、コストの大きい頂点から確定させていく。

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!
 
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
 
typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;
 
V dijkstra(const Graph& G, int s) {
    int N = G.size();
    priority_queue<Pii> pq;   // cost, vertex (!!!今回はcostの""降順""!!!)
    V d(N, -1);
    d[s] = s;
    pq.push(make_pair(s, s));
 
    while (!pq.empty()) {
        auto p = pq.top(); pq.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (const int& u : G[v]) {
            int nd = min(d[v], u);
            if (d[u] < nd) {
                d[u] = nd;
                pq.push(Pii(d[u], u));
            }
        }
    }
    return d;
}
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
 
    int N, M, s;
    cin >> N >> M >> s;
    s--;
    Graph G(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
 
    auto d = dijkstra(G, s);
 
 
    rep(i, N) {
        if (d[i] >= i) {
            cout << i + 1 << endl;
        }
    }
}

理解するのに1週間かかってしまった。