Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-12-29SRM492 Div1

SRM492 Div1 550 TimeTravellingTour

| 17:18 | SRM492 Div1 550 TimeTravellingTour - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM492 Div1 550 TimeTravellingTour - SRM diary(Sigmar) SRM492 Div1 550 TimeTravellingTour - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

うーん・・

始点と終点をmemo化して適当に再帰で解けそうな気がするけど

時間ない・・とりあえず書くか

→合わない。なんかループしてるし。ちょっと違う・・

→だめだ・・残り5分。修正できない。終わった


後で

分岐する都市を決めて、その都市まで行き、そこから訪問先を前半と後半に分けて再帰的に訪問することで解けます

整理すればなんということはないが整理する時間が足りない

正直250に時間かけ過ぎると全然無理すぎるしもうちょっと簡単にしてほしい・・

計算量がO(n^5)なんだが・・最大ケース1秒くらいです


ソースコード

const ll INF=100000000000000000LL;
ll memo[52][52][52];

template <class T> vector <T> strspl(string str, char delim) {
	vector <T> res;
	stringstream ss(str);
	string s;
	while(std::getline(ss, s, delim)) {
		if(ss.fail()) continue;
		stringstream sst(s);
		T tmp;
		sst >> tmp;
		if(sst.fail()) continue;
		res.push_back(tmp);
	}
	return res;
}

class TimeTravellingTour {
public:
	int n, m;
	vector <int> city;
	ll cost[52][52];

	//都市curから、beginからendまでの都市を訪問する
	ll rec(int begin, int end, int cur) {
		ll res=INF;
		if(end-begin==1) return cost[cur][city[begin]];
		if(memo[begin][end][cur]>=0) return memo[begin][end][cur];
		for(int fork=0; fork<n; fork++) {
			for(int partition=begin+1; partition<end; partition++) {
				res=min(res, cost[cur][fork]+rec(begin, partition, fork)+rec(partition, end, fork));
			}
		}
		memo[begin][end][cur]=res;
		return res;
	}

	long long determineCost(int N, vector <int> city, vector <string> road) {
		long long res=INF;

		n=N;
		this->city=city;
		m=city.size();
		memset(memo, -1, sizeof(memo));
		for(int i=0; i<n; i++) for(int j=0; j<n; j++) cost[i][j]=INF;
		for(int i=0; i<n; i++) cost[i][i]=0;

		//parse
		string s=accumulate(road.begin(), road.end(), string());
		vector <string> vs=strspl <string>(s, ' ');
		for(int i=0; i<(int)vs.size(); i++) {
			vector <int> vi=strspl <int>(vs[i], ',');
			cost[vi[0]][vi[1]]=cost[vi[1]][vi[0]]=vi[2];
		}

		//warshall-floyd
		for(int k=0; k<n; k++) {
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					cost[i][j]=min(cost[i][j], cost[i][k]+cost[k][j]);
				}
			}
		}

		res=rec(0, m, 0);
		if(res>=INF) res=-1;
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101229