SRM583 Div1 Easy

250

WFとか。
range[i]が頂点の数より大きくなる場合がある。
(i - range[i] + V) % Vだと負になったりする。

class TravelOnMars {
public:
  int minTimes(vector <int> range, int startCity, int endCity)
  {
    const int N = range.size() + 10;
    int g[N][N];
    const int inf = 1 << 28;
    fill(&g[0][0], &g[N - 1][N - 1] + 1, inf);
    const int M = range.size();
    for (int i = 0; i < M; ++i) {
      for (int j = -range[i]; j <= +range[i]; ++j) {
        int k = (i + j + M * M) % M;
        g[i][k] = 1;
      }
    }
    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]);
        }
      }
    }
    return g[startCity][endCity];
  }