TopCoder SRM 642 Div2 Hard TallShoes

Div2Hardにしては簡単かも。
http://community.topcoder.com/stat?c=problem_statement&pm=13523

問題

N頂点と有向辺からなるグラフがある。
各辺には高さh[i]が設定されている。

ここで王様が頂点0から頂点(N-1)まで辺を辿って移動することを考える。
ただし、靴の高さをHとすると、辺の高さh[i]がH以上の辺しか移動できない。
なお、各辺の高さh[i]は、x^2のコストを払いh[i]+xにすることができる。

最大コストB以下の範囲で辺の高さを変え、できるだけ高い靴で頂点(N-1)に移動したい。
靴の高さHの最高値を答えよ。

解法

靴の高さHを二分探索する。
その際h[i]＜Hの辺に対しては(H-h[i])^2のコストで移動できると考えてダイクストラ法を行えばよい。

class TallShoes {
	public:
	int mat[51][51], N;
	ll B;
	
	int ok(int H) {
		int i;
		ll mon[51];
		MINUS(mon);
		
		mon[0]=B;
		priority_queue<pair<ll,int> > Q;
		Q.push(make_pair(B,0));
		while(Q.size()) {
			ll m=Q.top().first;
			int cur=Q.top().second;
			Q.pop();
			if(mon[cur]!=m) continue;
			FOR(i,N) if(i!=cur && mat[i][cur]>=0) {
				ll c=max(H-mat[i][cur],0);
				c=c*c;
				if(mon[i]<m-c) mon[i]=m-c,Q.push(make_pair(mon[i],i));
			}
			
		}
		
		return mon[N-1]>=0;
	}
	
	int maxHeight(int N, vector <int> X, vector <int> Y, vector <int> height, long long B) {
		int i,x,y;
		MINUS(mat);
		FOR(i,X.size()) mat[X[i]][Y[i]]=mat[Y[i]][X[i]]=height[i];
		
		this->N=N;
		this->B=B;
		int ret=0;
		for(i=30;i>=0;i--) if(ok(ret+(1<<i))) ret += 1<<i;
		return ret;
	}
}

まとめ

二分探索に気づけば、後は単純。