SRM 583 Div1 Easy TravelOnMars

問題

Nの都市が円状に存在している。i番目の都市は前後range[i]個の都市との間に一方向の道路が敷設されている。startCityからEndCityに訪れるために必要な最小の通過道路数を返せ。

やりかた

N - 1と0番目の都市が隣り合っていることに注意しつつ、ただのグラフ最短路問題。幅優先探索でもOK。

以下ソース。

int d[60][60];

class TravelOnMars {
public:
  int minTimes(vector <int> range, int startCity, int endCity) {
    for(int i = 0; i < 60; i++) fill(d[i], d[i] + 60, INF);

    int N = range.size();
    for(int i = 0; i < N; i++){
      for(int j = -range[i]; j <= range[i]; j++){
	int idx = i - j;
	while(idx < 0) idx += N;
	while(idx >= N) idx -= N;
	d[i][idx] = 1;
      }
    }
    for(int k = 0; k < N; k++)
    for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
      d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    return d[startCity][endCity];
  }
};