SRM583 Div1 Easy "TravelOnMars"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12608

訳

ボブは現在火星に行っている。

火星にはN個の都市があった。これらの全ての都市は円状の鉄道で繋がっており、0からN-1の番号がつけられている。より正確には、鉄道は0と1, 1と2..., N-2とN-1, N-1と0というふうに都市を繋いでいる。列車はどちらの方向にも通行できる。

あなたはN個の要素を持つint[] rangeが与えられる。range[i]はi番目の都市が何個離れた都市まで直通電車が運行しているかを表すものである。（例えば、N=17でrange[2]=3であれば、この都市から{16,0,1,2,3,4,5}の都市に直通電車が走っている）

あなたはまたint startCityとendCityが与えられる。ボブはstartCity番の都市から出発し、endCity番の都市まで旅行する。乗り継がなくてはならない最小の列車の数を返せ。

制約

2 <= N <= 50

考えた事

グラフを作ってワーシャルフロイド

事後

どちらの方向にも通行できるのか、一方通行なのか分かりにくいなこの訳
直通電車はどうも一方通行っぽいです

ソースコード

const int INF = 1000000;
int n;
int G[55][55];

class TravelOnMars {
public:
    int minTimes(vector <int> range, int startCity, int endCity){
        int n = range.size();

        // i -> j
        for( int i = 0; i < n; i++ ){
            for( int j = 0; j < n; j++ ){
                int t1 = i;
                int t2 = j;
                if( t1 < t2 ) swap( t1, t2 );
                int len = min( t1 - t2, t2 - t1 + n );
                if( len <= range[i] ){
                    G[i][j] = 1;
                }else{
                    G[i][j] = INF;
                }
            }
        }

        // ワーシャルたん
        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];
    }
};