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
考えた事
まず、友人関係のグラフが連結してなければ無限大になる。
そうでなければ、任意の2市民における、最短距離の最大のやつ * 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; } };