topcoder

kojingharangの日記

2013-07-10

SRM 584 Div1 250 Egalitarianism

00:30 |

友達関係が Y/N で与えられる。自分の所持金は友達の所持金±D以内じゃないといけない。人々の所持金の最大差を求める問題。
人数≦50

ある人とある人が何ホップでつながってるか分かれば、そのホップ数 x D の最大値が答え。
Warshall-Floyd さん

accepted

class Egalitarianism {
	public:
	int maxDifference(vector <string> F, int D) {
		int N=F.size();
		ll INF = 1LL<<50;
		VVI w(N, VI(N, INF));
		REP(i, N) w[i][i] = 0;
		REP(i, N) REP(j, N) if(F[i][j]=='Y') w[i][j] = 1;
		REP(k, N) REP(i, N) REP(j, N) w[i][j]=min(w[i][j], w[i][k]+w[k][j]);
		ll d = 0;
		REP(i, N) REP(j, N) d=max(d, w[i][j]);
		return d==INF ? -1 : d*D;
	}
};