TopCoder SRM417 Div1Hard

問題

平面上にいくつかの点があり、いくつかの点の間は道で結ばれている。道同士は端点以外で交差しない（しても接続しない）。2点間の最短距離は、道の上のみを通り、接続点のみで道を変えたときの最短距離である。道の上から2点選ぶとき、最短距離の最大値を求めよ。

解法

まず点の間でWarshal-Floyd。
その後、「2点間の最短距離」、「3点A,B,CでA--B--C--Aの最短距離の半分」、「4点A,B,C,Dでmin(A--B--C--D--A,A--B--D--C--A)/2」とすればよい。適当

コード

#include <vector>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

class WalkingDistance
{
public:
	double getLongestShortest(vector<int> X, vector<int> Y, vector<string> S)
	{
		double ld[50][50], dist[50][50];
		for(int i=0;i<S.size();i++){
			for(int j=0;j<S.size();j++){
				if(i==j) dist[i][j] = 0;
				else{
					if(S[i][j]=='Y') dist[i][j] = sqrt(0.0 + (X[i]-X[j])*(X[i]-X[j]) + (Y[i]-Y[j])*(Y[i]-Y[j]));
					else dist[i][j] = 10000000;
				}
				ld[i][j] = dist[i][j];
			}
		}
		for(int i=0;i<S.size();i++){
			for(int j=0;j<S.size();j++){
				for(int k=0;k<S.size();k++){
					dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
				}
			}
		}
		
		double ret = 0;
		for(int i=0;i<S.size();i++){
			for(int j=0;j<S.size();j++){
				ret = max(ret, dist[i][j]);
			}
		}
		for(int i=0;i<S.size();i++){
			for(int j=0;j<S.size();j++) if(ld[j][i]>0&&ld[j][i]<5000){
				for(int k=0;k<S.size();k++) if(i!=k&&j!=k){
					for(int l=0;l<S.size();l++) if(ld[k][l]>0&&ld[k][l]<5000&&j!=l&&k!=l){
						ret = max(ret, min(dist[i][j]+dist[j][k]+dist[k][l]+dist[l][i],dist[i][j]+dist[j][l]+dist[l][k]+dist[k][i])/2);
					}
				}
			}
		}
		
		return ret;
	}
};