ARC 056 B

今回はこの問題です。

arc056.contest.atcoder.jp

n箇所の駐車場所があります。お互いにm本の道によってつながっています。s番目の駐車場所が駐車場の入り口になっています。1番からn番目の人が順番に駐車していきます。i番目の人はi番目の駐車場所に駐車します。すでに駐車された場所はとおることができません。このとき、自分の決められた場所に駐車できる人の番号を降順に求めてください、という問題です。

解けなかったので解説を見てときました。回答はこんな感じです。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define pai 3.14159265359
    #define mod 1000000007
     
    int main()
    {
        int n, m, s;
        cin >> n >> m >> s;
        vector<vector<int> > road(200001);
        for(int i = 0; i < m; i++){
            int u, v;
            cin >> u >> v;
            road[u].push_back(v);
            road[v].push_back(u);
        }
        vector<int> ans;
        vector<int> minnum_mustgo(n + 1, 0);
        minnum_mustgo[s] = s;
        priority_queue<int> qu;
        qu.push(s);
        while(!qu.empty()){
            int nowplace = qu.top();
            // cout << nowplace << " " << minnum_mustgo[nowplace] << endl;
            qu.pop();
            for(int i = 0; i < road[nowplace].size(); i++){
                int nextplace = road[nowplace][i];
                if(min(minnum_mustgo[nowplace], nextplace) > minnum_mustgo[nextplace]){
                    minnum_mustgo[nextplace] = min(minnum_mustgo[nowplace], nextplace);
                    qu.push(nextplace);
                }
            }
        }
        for(int i = 1; i <= n; i++){
           if(minnum_mustgo[i] >= i)  cout << i << endl;
        }
        return 0;
    }

minnum_mustgo[i]は駐車場の入り口からi番目の駐車場所に移動するのに通らないといけない駐車場所のうち最小の番号が記録されます。この番号がiよりも小さければ、すでに車が止められた場所を通らないと車を止められない、したがって車を止められないということになります。
minnum_mustgo[i]をダイクストラ法を用いてもとめていきます。min(minnum_mustgo[nowplace], nextplace)は入り口からnowplaceに行くのに通らなければいけない駐車場所のうちの最小の番号と、次に通る場所の番号のうち小さいもの、つまり入り口からnextplaceへ行くのに通らないといけない駐車場所のうち最小の番号となります。priority_queueでは値の大きいものから順に取り出されるので、大きい番号の駐車場所ばかり通っていく道から順に見つかっていきます(と思います)。

解説を理解するのに少し時間がかかりました…難しかったです。