TopCoder SRM 573 Div1 Medium SkiResorts

さてMedium。
本番、考え方は良かったのにツメが甘くてミス。
うーん、もったいない。
http://community.topcoder.com/stat?c=problem_statement&pm=12468

問題

N個のポイントからなるスキー場がある。
N個のポイントで相互に行き来できるかどうかの情報と、各ポイントの高さが与えられる。
各ポイントは、相互に行き来でき、かつ移動元より移動先の高さが等しいか低い場合、移動可能である。

なお各ポイントは、コスト1で高さを1変えられる。
このときポイント0からポイント(N-1)に到達するための最小コストを求める。

解法

各ポイントは高さを下げた方がいい場合（山を越える場合）もあれば上げた方がいい場合（谷を超える場合）もあるので、単純に上げる・下げるだけではだめ。

ここで考えてみると、各ポイントの高さは0～10^9と色々取れるけど、実質的にはN個のポイントと等しいN通り以外の高さをとってもしょうがないことになる。
よって、NポイントがN通りの高さを取ると考え、N^2個の点を持つグラフでの最小コストを求めればよい。

ll MA=1LL<<50;

class SkiResorts {
	public:
	int N;
	vector<int> E[51*51];
	vector<int> A;
	int vis[3000];
	ll cost[3000];
	int ds[60][60];
	
	long long minCost(vector <string> road, vector <int> altitude) {
		int x,y,z,w;
		A=altitude;
		N=A.size();
		
		FOR(x,51*51) E[x].clear();
		FOR(x,N) FOR(y,N) ds[x][y]=abs(A[x]-A[y]);
		
		//最初の高さ
		FOR(x,N) E[0].push_back(x);
		
		FOR(x,N) FOR(y,N) if(road[x][y]=='Y') {
			FOR(z,N) FOR(w,N) if(A[z]>=A[w]) E[x*50+z].push_back(y*50+w);
		}
		
		FOR(x,3000) cost[x]=MA;
		cost[0]=0;
		
		ZERO(vis);
		set<pair<ll,int> > S;
		S.insert(make_pair(0,0));
		while(!S.empty()) {
			set<pair<ll,int> >::iterator sit=S.begin();
			pair<ll,int> p=*sit;
			S.erase(sit);
			
			int cur=p.second;
			vis[cur]=1;
			int tar,i;
			FOR(i,E[cur].size()){
				int tar=E[cur][i];
				ll nc=cost[cur] + ds[tar%50][tar/50];
				if(nc < cost[tar]) S.insert(make_pair(cost[tar]=nc,tar));
			}
		}
		
		ll res=MA;
		FOR(x,N) res = min(res,cost[(N-1)*50+x]);
		if(res==MA) res=-1;
		return res;
	}

};

まとめ

最初、辺にコストを持たせたらメモリが64MBからあふれてしまった。
コストは結局移動先の点の高さで決まるので、辺にコストを持たせず、移動先の点の高さから計算させることでメモリ消費を回避した。
うーん、本番でこういうしょうもないミスは避けたいなぁ。