TopCoder SRM 583 Div1 Easy TravelOnMars

問題

環状にn個の駅がある。
i番目の駅は、距離がrange[i]以下の、前と後ろの駅全てに対して直通の電車が走っている。
startCity番の駅からendCity番の駅まで、最低何本の電車に乗ればいけるか求めよ。

制約条件

n≦50
range[i]≦50

方針

グラフを作って最短路。(ワーシャルフロイドなど)
rangeが大きいので適当にやると配列を突き抜けたりしてしまうことに注意。

ソースコード

class TravelOnMars {
	public:
	int minTimes(vector <int> range, int startCity, int endCity) {
		
		int n = range.size();
		int d[50][50];
		
		rep(i, n) rep(j, n) d[i][j] = inf;
		
		rep(i, n){
			d[i][i] = 0;
			
			rep(j, min(n - 1, range[i])){
				d[i][(i + j + 1) % n] = 1;
				d[i][(i + n - (j + 1)) % n] = 1;
			}
		}
		rep(k, n) rep(i, n) rep(j, n) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
		
		return d[startCity][endCity];
	}
};