SRM 584 Div1 Easy / Div2 Medium Egalitarianism

問題

N人の人間がいて、おのおの金を持っている。彼らの友好関係がvector string で与えられる。i番目の行のj番目が'Y'ならiとjは友人。'N'なら友人ではないとする。そして直接の友人間では持ち金の差は大きくともdとなるように調整されている。N人の持金の最大金額と最小金額の差の最大値を求めよ。いくらでも大きくできるときは-1を返せ。

やりかた

友人関係はグラフとして表現できる。グラフが連結でない時には連結していないノード間でいくらでも金額差を大きくできるので-1。つまりすごくリッチなグループをすごく貧乏なグループの差をいくらでも大きくできてしまう。
連結であれば点対間の最短距離が最長になるような２つのノード（人）が最も豊かな人と最も貧しい人になる。そしてその差も最大になる。なのでこの２点の距離 * dが答え。

全点対間の最短距離でN <= 50なのでワーシャル＝フロイドでOK。
ある点対間の最短距離がINFなら非連結とわかる。

以下ソース。

int dist[50][50];

class Egalitarianism {
public:
  int maxDifference(vector <string> isFriend, int d) {
    memset(dist, 0, sizeof(dist));
    for(int i = 0; i < 50; i++)
      for(int j = 0; j < 50; j++)
	if(i != j)
	  dist[i][j] = INF;
    
    int N = isFriend.size();
    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++){
	if(isFriend[i][j] == 'Y') dist[i][j] = 1;
      }

    for(int k = 0; k < N; k++)
      for(int i = 0; i < N; i++)
	for(int j = 0; j < N; j++)
	  dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    

    int ans = -1;
    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++)
	ans = max(ans, dist[i][j]);
    
    return ans >= INF ? -1 : ans * d;
  }
};