Codeforces #163 Div2. D. BerDonalds

さて本番中に解き切れなかったDへ。
http://codeforces.com/contest/266/problem/D

最大N点(<=200)からなるグラフが与えられる。各辺は長さを持つ。
グラフの点または辺上のうち、そのグラフの各点にたどり着く場合に最も遠い点までの距離が最短となる場所を求めて、最遠点までの距離を返す問題。

そのような場所がグラフの点上にある場合は簡単である。
N<=200と点が少ないので、まずFloyd法で各２点間の距離を求める。
そして各点を求める場所の候補とし、他の点までの距離の最大値が最も小さくなる点を選べばよい。

ただ、テストケース3の様に辺の途中に場所が来る場合がある。
点A,Bを結ぶ長さLの辺があるとする。
各点Cに対し、Floyd法で求めたA-C間の距離とB-C間の距離の差がLより小さい場合、この辺の途中にA経由でCに到達するのとB経由でCに到達するのが均衡する位置がある。
このような位置は、Cに到達するまでの距離が最も遠い。

同様に他の点においても、A-B上Cに到達するまでの距離が最も遠い点を求める。
これらの点から、距離を最小化できる位置を求めることができる。

書いたコードはO(N^3)～O(N^4)位だけど、なんとか3.7sで回答。
なお、この問題の回答は少数になるとはいえ、0.5単位の答えしか出てこない。
そのため、最初に長さを2倍して整数で計算し、最後に2で割った方が誤差が累積して出てこなくて良い。

int N,M;
vector<pair<int,ll> > edge[201];
ll dist[201][201];

void solve() {
	int f,r,i,j,k,cur,tar,ret;
	ll l;
	int x,y,mx,my;
	
	MINUS(dist);
	GET2(&N,&M);
	FOR(i,M) {
		x=GETi()-1;
		y=GETi()-1;
		l=GETi()*4;
		edge[x].push_back(make_pair(y,l));
		edge[y].push_back(make_pair(x,l));
		dist[x][y]=dist[y][x]=l;
	}
	FOR(i,N) dist[i][i]=0;
	
	FOR(i,N) {
		FOR(j,N) FOR(k,N) {
			if(dist[j][i]>=0 && dist[i][k]>=0 && (dist[j][k]>dist[j][i]+dist[i][k] || dist[j][k]==-1))
				dist[j][k]=dist[j][i]+dist[i][k];
		}
	}
	
	ll mi=1LL<<40;
	//ten
	FOR(i,N) {
		ll ma=0;
		FOR(j,N) ma=max(ma,dist[i][j]);
		mi = min(mi, ma);
	}
	
	//hen
	vector<int> cand,maxd;
	FOR(i,N) {
		FOR(j,edge[i].size()) {
			int to=edge[i][j].first;
			if(to<i) continue;
			ll rl=edge[i][j].second;
			
			cand.clear();
			maxd.clear();
			cand.push_back(0);
			cand.push_back(rl);
			FOR(k,N) {
				if(abs(dist[i][k] - dist[to][k])<rl) 
					cand.push_back((dist[i][k]+rl + dist[to][k])/2-(dist[i][k]));
			}
			
			sort(cand.begin(),cand.end());
			cand.erase(unique(cand.begin(),cand.end()),cand.end());
			if(cand.empty()) continue;
			
			FOR(k,cand.size()) {
				rl=cand[k];
				ll tl=0;
				FOR(f,N) {
					tl = max(tl, min(dist[i][f]+rl,dist[to][f]+edge[i][j].second-rl));
				}
				maxd.push_back(tl);
				mi = min(mi,tl);
			}
			FOR(k,cand.size()-1) {
				if(cand[k+1]-cand[k] != abs(maxd[k+1]-maxd[k])) {
					mi = min(mi,((ll)maxd[k+1]+maxd[k]-(cand[k+1]-cand[k]))/2);
				}
			}
			
			
			
		}
	}
	_P("%.10lf\n",mi/4.0);
	
	return;
}

まとめ

グラフの各点への最遠路を最短化するという問題。
これだけならよくありそうだけど、点だけでなく辺上も答えになりうることで適度に難易度が上がって面白くなった。
いや自力で解けて良かった。