DistanceZeroAndOne [TopCoderOpen 2017 Round2A Div1 Med]

https://community.topcoder.com/stat?c=problem_statement&pm=14596

問題概要

N頂点の連結な無向グラフがある。
これについて、頂点0から各頂点への距離dist0と頂点1から各頂点への距離dist1が分かっている。
2つの距離が満たされる無向グラフがあれば復元せよ。

解説

既出らしい。
CODE FESTIVAL 2016 Exhibition A. Distance Pairs
この問題での解法は貪欲法だが、この問題でも貪欲法を使う。
voidmaxさんの解法を参考に書いたが、こんな貪欲法で本当に通るの？って感じ。
でもプロはみんなこの解法。
コードを見てみれば早いが、「abs(d0[i] - d0[j]) <= 1 && abs(d1[i] - d1[j]) <= 1」ならば辺を頂点i,j間に辺を張るという貪欲法をやっていく。
あとは、それで正しく構築できているかをワーシャルフロイドで距離を測って、比較する。

struct DistanceZeroAndOne {
    vector <string> construct(vector <int> d0, vector <int> d1) {
        int n = d0.size();

        // init
        vector<string> res;
        rep(i, 0, n) { string s = ""; rep(j, 0, n) s += "N";  res.push_back(s); }

        // build
        rep(i, 0, n) rep(j, i + 1, n)
            if (abs(d0[i] - d0[j]) <= 1 && abs(d1[i] - d1[j]) <= 1)
                res[i][j] = res[j][i] = 'Y';

        // check
        vector<vector<int>> d(n, vector<int>(n, 10101010));
        rep(i, 0, n) d[i][i] = 0;
        rep(i, 0, n) rep(j, 0, n) if (res[i][j] == 'Y') d[i][j] = 1;
        rep(k, 0, n) rep(i, 0, n) rep(j, 0, n) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        rep(i, 0, n) if (d0[i] != d[0][i]) return {};
        rep(i, 0, n) if (d1[i] != d[1][i]) return {};

        return res;
    }
};