SRM584 Dvi1 Easy & Div2 Medium "Egalitarianism"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12613

訳

とある王国にはn人の市民がいる。彼らはそれぞれ貯金があり、それは負ではない整数で表される。

市民は0からn-1と番号付けられている。友人関係となっているものもいる。彼らの友人関係はString[] isFriend で説明される。isFriend[i][j] == 'Y'であれば、i番目とj番目の市民は友達であり、'N'であればそうではない。

王様は下記のような命令を出した。

友人同士では、貯金の差額が d より大きくなってはならない。
言い換えれば、ある市民がxドル貯金を持っていたら、
彼の友達の貯金はx-dを下回っててはならないしx+dを上回っててはならない。

市民の数と、友人関係の情報が与えられる。この情報を元にしたとき、全市民間の貯金の最大差額はいくらになるかを返せ。無限大になるのであれば-1を返せ。

制約

2 <= n <= 50
1 <= d <= 1000

考えた事

まず、友人関係のグラフが連結してなければ無限大になる。

そうでなければ、任意の２市民における、最短距離の最大のやつ * d

ソースコード

const int INF = 50 * 1000 * 10;
int G[55][55];

class Egalitarianism {
public:

    int maxDifference(vector <string> isFriend, int d){
        int n = isFriend.size();
        for( int i = 0; i < n; i++ ){
            for( int j = 0; j < n; j++ ){
                if( i == j ){
                    G[i][j] = 0;
                }else if( isFriend[i][j] == 'Y' ){
                    G[i][j] = d;
                }else{
                    G[i][j] = INF;
                }
            }
        }

        // ワーシャルたん
        for( int k = 0; k < n; k++ ){
            for( int i = 0; i < n; i++ ){
                for( int j = 0; j < n; j++ ){
                    G[i][j] = min( G[i][j], G[i][k] + G[k][j] );
                }
            }
        }

        // 最大の最短距離をとる
        int ans = 0;
        for( int i = 0; i < n; i++ ){
            for( int j = 0; j < n; j++ ){
                ans = max( ans, G[i][j] );
            }
        }

        if( ans >= INF ) ans = -1;
        return ans;
    }
};