SRM 492 DIV1 Medium TimeTravellingTour

http://apps.topcoder.com/stat?c=problem_statement&pm=10782&rd=14245

解答

この中の時間を基準に考えたら、時間の分岐が木になることがわかった。分岐がタイムトラベルポイントで、葉が訪れる街。
その木を左右に分割して探索していく。
この解法はO(n^5)だが、いくらかの定数倍速いのでぎりぎり間に合う。O(n^4)解法もあるらしい

コメント

DIV1 Medium自分で解けた！しかも結構難しい問題だったらしい。気持ちがいい！
実際に本番でやることになっていた場合、Easyとあわせてギリギリ間に合う程度の時間でできたらしい。もう少し早く解けるほうがいいね。
今はEasy半分より大きい程度の割合で解ける程度の感じだけど、このくらいをある程度解けるようになりたいねー

コード

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define aut(v, x) __typeof(x) v = (x)
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii;
const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL;

ll d[55][55];
ll dp[55][55][55];
struct TimeTravellingTour {
	vi t; int N;
	ll rec(int i, int l, int u) {
		if(dp[i][l][u]!=-1)return dp[i][l][u];
		ll r = INFL;
		if(l == u) {
			r = d[i][t[l]];
		}else {
			rep(k, N) if(d[i][k]!=INFL) {
				reu(s, l, u) {
					ll x = d[i][k], y;
					y = rec(k, l, s);
					if(y == INFL) continue;
					x += y;
					y = rec(k, s+1, u);
					if(y == INFL) continue;
					x += y;
					r = min(r, x);
				}
			}
		}
		return dp[i][l][u] = r;
	}
	long long determineCost(int N_, vector <int> t_, vector <string> roads) {
		N = N_; t = t_;
		string rs;
		each(i,roads)rs+=*i;
		each(i,rs)if(*i==',')*i=' ';
		stringstream s(rs);
		int a,b,c;
		mset(d, (unsigned char)INFL);
		rep(i, N) d[i][i] = 0;
		while(s >> a >> b >> c) {
			d[a][b] = min(d[a][b], (ll)c);
			d[b][a] = min(d[b][a], (ll)c);
		}
		rep(k, N) rep(i, N) rep(j, N) {
			if(d[i][k] != INFL && d[k][j] != INFL)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
		}
		mset(dp, -1);
		ll r = rec(0, 0, t.size()-1);
		return r == INFL ? -1 : r;
	}
};