SRM583 Div1 Easy わーしゃるなふろいどさんで試す

TravelOnMars2.py

class TravelOnMars2:
    def minTimes(self, range, startCity, endCity):
        N = len(range)
        INF = 1000000
        dp = [[INF for _ in xrange(N)] for _ in xrange(N)]
        for i in xrange(N):
            for j in xrange(N):
                l = (i - j + N) % N
                r = (j - i + N) % N
                if min(l, r) <= range[i]:
                    dp[i][j] = 1
            print dp

        for k in xrange(N):
            for i in xrange(N):
                for j in xrange(N):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

        return dp[startCity][endCity]