TopCoder SRM 584 Div1 Easy Egalitarianism

問題

n人の人がいて、isFriend[i][j]が'Y'であるときi, jは友達同士である。
(i, jが友達のときj, iも友達である)


友達同士の所持金の差はd以下である。
このとき、n人の中で、所持金の最大値と最小値の差は、最大でいくらになるか。


最大値が存在しないときは-1を返せ。

制約条件

n≦50
d≦1000

方針

最小値になる人を決めて牛ゲーした。(寝ぼけていた)


本当は、最小値になる人を決めたら牛ゲーしなくても、最短距離が一番遠い人の距離 * dが最大値になる。
これを全ての最小値になる人について試せばよい。

ソースコード

class Egalitarianism {
	public:
	int maxDifference(vector <string> isFriend, int d) {
		
		
		int n = isFriend.size();
		int e[50][50], dist[50];
		
		rep(i, n) rep(j, n) e[i][j] = i == j ? 0 : inf;
		rep(i, n) rep(j, n){
			if(isFriend[i][j] == 'N') continue;
			
			e[j][i] = min(e[j][i], d);
			e[i][j] = min(e[i][j], d);
		}
		
		ll ans = 0;
		rep(zero, n){
			rep(i, n) dist[i] = i == zero ? 0 : inf;
			rep(it, n){
				bool update = 0;
				rep(i, n) rep(j, n) if(dist[i] > dist[j] + e[j][i]){
					
					update = 1;
					dist[i] = dist[j] + e[j][i];
					if(it == n - 1) return -2;
				}
				if(!update) break;
			}
			ll res = *max_element(dist, dist + n) - *min_element(dist, dist+ n);
			ans = max(ans, res);
		}
		if(ans == inf) return -1;
		return ans;
	}
};