SRM 426 div1 hard:LongStraightRoad

牛ゲーという単語を初めて聞いた。

問題

TopCoder Statistics - Problem Statement

解法

牛ゲーというのは,

とある線形計画問題について,制約が
d[u] <= d[v]+w　・・・①
という形で,また最小化したい値が
d[t]
というようにおける時,この問題の答えは

①で表されるそれぞれの制約について v から u にコストwの辺を貼ったときのスタート地点sからtへの最短距離として求めることができる

というものです(多分)。
今回の問題をこのような形に落とし込んでみましょう。

まずすべてのsignは友人が順番に示してくれているということなので,signの数をnとすると, i = 0〜n-2について,

d[i] < d[i+1] d[i] + 1 <= d[i+1] d[i] <= d[i+1] - 1

よって,頂点i+1から頂点iに向かってコスト-1の辺を貼ります。

また,各場所について,i番目のsignがj番目の場所への距離がcであると示しているとすると,

d[n+j] - d[i] = c c <= d[n+j] - d[i] <= c d[i] <= d[n+j]-c かつ d[n+j] <= d[i] + c

よって,n+jからiにコスト-cの辺を,iからn+jにコストcの辺を貼ります。
これで今いる位置d[n-1] = 0からの距離を求めればひとまず形としては問題を解いています。あとは細かいところを詰めていきます。

まずdestinationがどこのsignにも書かれてなかったりすると,どうしようもありません。ここらへんはUnionFind木で管理してます。
また,道中で手前にあるはずのsign[i]がsign[i+1]よりも後ろにあることになってたりしてもダメですね。
またdestinationがすでに通りすぎてることになってる(d[destination] < 0)でもダメです(友人氏気づけよ)。
この時-1を返すことも考慮すると答えが得られます。

以下ソースコード。Mi_Sawaさんのコードを参考にしました(というか完全に写経)。なんで10000でかけたり割ったりしないとWAになるのかはよくわかってないです(8割方理解できた気になったのでとりあえず今回はいいやと言った感じです,すみません)。

vector<string> split(const string& s, const char& del) {
    vector<string> res;
    int p = 0, q;
    while ((q = s.find_first_of(del, p)) != string::npos) {
        res.emplace_back(s.substr(p, q-p));
        p = q+1;
    }
    res.emplace_back(s.substr(p));
    return res;
}

struct E {
    int t;
    ll c;
    E(int t, ll c) : t(t), c(c) {}
};

struct UnionFind {
    vector<int> par;
    int n, cnt;
    UnionFind(const int& x = 0) {init(x);}
    void init(const int& x) {par.assign(cnt=n=x, -1);}
    inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);}
    inline bool same(const int& x, const int& y) {return find(x) == find(y);}
    inline bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return false;
        --cnt;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline int count() const {return cnt;}
    inline int count(int x) {return -par[find(x)];}
};

class LongStraightRoad {
public:
    int distanceToDestination(vector <string> signs, string destination) {
        map<string, int> enc;
        int n = signs.size();
        enc[destination] = n;
        vector<vector<E> > g(n);
        for (int i = 0; i < n; i++) {
            for (auto &s : split(signs[i], ';')) {
                stringstream ss(s);
                string name; ll cost;
                ss >> name >> cost;
                cost *= 10000;
                if (!enc.count(name)) {
                    int x = enc.size() + n;
                    enc[name] = x;
                }
                g[i].emplace_back(enc[name], cost);
            }
        }
        g.resize(n + enc.size());

        // destinationが一人で浮いてたら死
        UnionFind uf(g.size());
        for (int u = 0; u < n; u++) {
            for (auto &e : g[u]) uf.unite(u, e.t);
        }
        if (!uf.same(n-1, n)) return -1;

        // グラフの構成
        for (int u = 0; u < n; u++) {
            for (auto &e : g[u]) g[e.t].emplace_back(u, -e.c);
        }
        for (int u = 0; u < n-1; u++) {
            g[u+1].emplace_back(u, -1);
        }

        // warshall floydおじさん
        const int N = g.size();
        vector<ll> d(N, numeric_limits<ll>::max() / 4);
        d[n-1] = 0;
        for (int i = 0; i < N+2; i++) {
            bool cont = false;
            for (int u = 0; u < N; u++) {
                for (auto &e : g[u]) {
                    if (d[e.t] > d[u]+e.c) {
                        d[e.t] = d[u] + e.c;
                        cont = true;
                    }
                }
            }
            if (!cont) break;
            if (i == N+1) return -1;
        }
        for (int u = 0; u < N; u++) {
            if (d[u] < d[0]) return -1;
        }
        for (int u = 0; u < n-1; u++) if (d[u+1] <= d[u]) return -1;
        if (d[enc[destination]] < 0) return -1;
        return d[enc[destination]] / 10000;
    }
};