TopCoder SRM 583, Division 1, Level 1 : TravelOnMars

問題文

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

概要

リング状に N 個の街がある。
i 番目の町からは距離 以内の街へ一回で移動できる。
スタート地点とゴール地点が与えられたとき、最小で何回移動する必要があるか求めよ。

解法

街を頂点、一回の移動をコスト 1 の辺とするグラフを考えます。
このグラフ上でスタートからゴールまでの最短路が答えです。
辺のコストが全て 1 なので、BFS を用いることができます。

コード

typedef vector<int> VI;
typedef pair<int,int> PII;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define fst first
#define snd second

const int INF = INT_MAX / 4;

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

		priority_queue< PII, vector<PII>, greater<PII> > que;
		que.push( MP( 0, startCity ) );

		VI distance( N, INF );
		distance[ startCity ] = 0;

		while ( !que.empty() )
		{
			PII cur = que.top();
			que.pop();

			if ( distance[ cur.snd ] < cur.fst )
			{
				continue;
			}

			{ // left
				REP( i, 1, range[ cur.snd ] + 1 )
				{
					int next = ( cur.snd + N * 50 - i ) % N;
					if ( cur.fst + 1 < distance[ next ] )
					{
						distance[ next ] = cur.fst + 1;
						que.push( MP( cur.fst + 1, next ) );
					}
				}
			}
			{ // right
				REP( i, 1, range[ cur.snd ] + 1 )
				{
					int next = ( cur.snd + i ) % N;
					if ( cur.fst + 1 < distance[ next ] )
					{
						distance[ next ] = cur.fst + 1;
						que.push( MP( cur.fst + 1, next ) );
					}
				}
			}
		}

		return distance[ endCity ];
	}
};