SRM 652 div med: MaliciousPath

よくこんなの思いつくなぁ。

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13596&rd=16316

解法:まず直感的に思いつくのは、状態としてdp[n][k] = (頂点nにいて,Bobが残りk個のtokenを持っている時の解)を用意して、メモ化再帰的に解くというやり方。これを正直に実装するとdfs(n, k)でループができてしまい、全くうまく行かない。
そこで、kを1つずつ増やしていき、dp[n][k]を求めるときは、dp[i][k-1](i = 0...N-1)を利用することを考える。やり方としては、
①まずAliceがその時点での(K = kとしたときの)最短距離を求める。
②Bobは距離を最大化したいので、それを妨害する。具体的には、その時点での距離dist[x]に対して、bound[x]という量を用意して、bound[x] = max(w(x, y) + dist[y])とする(これはBobがk+1回妨害していることを意味する)。
これを繰り返し行うことにより、答えを求めることができる。

以下ソースコード

using namespace std;

typedef long long ll;
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin();itr!=c.end();itr++)

const ll INF = 1ll<<60;

struct edge {
    int to;
    ll cost;
    edge() {}
    edge(int t, ll c) : to(t), cost(c) {}
};

vector<vector<edge> > graph;
vector<ll> dist, bound;

void dijkstra(int N) {
    dist = vector<ll>(N, INF);
    priority_queue<pair<ll, int> > que;
    que.push(make_pair(0, N-1));
    dist[N-1] = 0;
    while (!que.empty()) {
        auto now = que.top(); que.pop();
        int v = now.second;
        ll d = -now.first;
        if (dist[v] != d) continue;
        for (auto e : graph[v]) {
            ll cost = max(bound[e.to], d+e.cost);
            if (cost < dist[e.to]) {
                dist[e.to] = cost;
                que.push(make_pair(-cost, e.to));
            }
        }
    }
}

class MaliciousPath {
public:
    long long minPath(int N, int K, vector <int> from, vector <int> to, vector <int> cost) {
        graph.resize(N);
        dist.resize(N);
        bound.resize(N);
        int m = from.size();
        // 逆向きのグラフを張る
        for (int i = 0; i < m; i++) {
            graph[to[i]].push_back(edge(from[i], (ll)cost[i]));
        }
        for (int k = 0; k <= K; k++) {
            dijkstra(N);
            for (int v = 0; v < N; v++) {
                for (auto e : graph[v]) {
                    bound[e.to] = max(bound[e.to], dist[v] + e.cost);
                }
            }
        }
        ll ret = dist[0];
        if (ret >= INF) ret = -1;
        return ret;
    }
};