Codeforces#333 Div1 A問題

はじめに

Codeforces Round #333 Div. 1 Prob. A. The Two Routes

問題:http://codeforces.com/contest/601/problem/A

Codeforces Round #333 Div. 2 Prob. C. The Two Routes

問題:http://codeforces.com/contest/602/problem/C

頂点が共通、辺が排他的な2つのグラフについて、頂点でぶつからないように最短経路問題を解く

解けなかった。

考え方

線路がないところには道があるということを考えると、スタートとゴールを直接つなぐ辺が線路と道のどちらかに存在する。

つまり、頂点で車と電車がぶつかることはない。それぞれ幅優先してmaxとるだけ。

参考:http://codeforces.com/blog/entry/21755?#comment-264661

上記の事実に気付かずに本番中は単にシミュレーションする幅優先を書いていた。

単にシミュレーションすると空間計算量はO(頂点の数^2)だけど時間計算量がO(辺の数^2)になる。(バグっていてMLE、終了後に修正してTLE)

この問題を解いたことで幅優先の計算量を勘違いしていることに気付いた。

幅優先の時間計算量はO(辺の数)であって、O(頂点の数)ではない。(空間計算量がO(頂点の数))

よくある2D迷路での探索は、辺の数が頂点の数×4程度しかないから、時間計算量もO(頂点の数)になっていただけ。

参考:https://ja.wikipedia.org/wiki/%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

最近、わかったつもりでわかっていなかったことをよく発見するし詰めが甘い

解答

重み無し単純グラフはsetのvectorで持つのが好きだけど、グラフの種類によってAPIが変わるのってあんまりよくない気がするしライブラリ整備したい。

#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

template<class T = long long> constexpr T PINF(){ return std::numeric_limits<T>::max(); }
template<class T = long long> constexpr T MINF(){ return std::numeric_limits<T>::lowest(); }

class Query{
public:
    int a,t;
};

int bfs(vector<set<int>> &edges,int n){
    queue<Query> qs;
    int ret = PINF<int>();
    qs.push({0,0});
    vector<bool> is_searched(n,false);
    while(!qs.empty()){
        Query q = qs.front(); qs.pop();
        int a = q.a, t = q.t;
        if(a==(n-1)){ return t; }
        is_searched[a] = true;
        for(auto na : edges[a]){
            if(is_searched[na]==false){
                qs.push({na,t+1});
                is_searched[na]=true;
            }
        }
    }
    return PINF<int>();
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);

    int n,m;
    cin >> n >> m;
    int ui,vi;
    vector<set<int>> railways(n,set<int>());
    for(int i = 0; i < m; ++i){ //railwaysの辺
        cin >> ui >> vi;
        railways[ui-1].insert(vi-1);
        railways[vi-1].insert(ui-1);
    }

    vector<set<int>> roads(n,set<int>());
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(i==j) continue;
            if(railways[i].count(j)==0){ //railwaysの辺がないところにroadsの辺がある
                roads[i].insert(j);
            }
        }
    }
    int ret = max(bfs(roads,n),bfs(railways,n));
    if(ret==PINF<int>()) cout << -1 << endl;
    else cout << ret << endl;
    return 0;
}

テストケース

本番中にいろいろ作って試したけどどっかいった