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; } };