TopCoder SRM 573, Division 1, Level 1 : SkiResorts

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12468&rd=15493

概要

あるスキー場には、N 箇所の "場所" があり、いくつかの道によって繋がれている。
スキーでの移動は、同じ高さの場所か、より低い高さの場所にのみ可能である。
各場所の高さを変える操作ができ、高さを 1 変えるのに必要なコストが 1 である。
各場所を繋ぐ道と、各場所の高さの情報が与えられる。
場所 0 から場所 N - 1 へ移動できるようにするのに必要なコストの最小値を求めよ。
到達できない場合は -1 を返せ。

解法

高さが等しくても移動が可能なため、いずれの場所の高さとも異なるような高さに変更する操作は除外して考えることができます。
すると、考えなければならない高さの数は高々 N 個となり、各場所に対して高さの情報を付加しても全体で 通りの状態しかありません。
ここで、場所と高さのペアをノード、状態遷移をエッジとして、エッジの重みを必要なコストとするグラフを考えます。
このグラフに対していわゆる「拡張 Dijkstara 法」で最短経路問題を解くことで答えが求まります。
（噂によると、グラフが密になるので の実装をした方がよいようです）
普通に通ったのでコード差し替えました（3/16）
（ 実装の方が好き && 本質的でない部分をプライオリティーキューに委託できるので）

FPSA でも書いてみました。

コード（ Dijkstra 法）

typedef long long LL;
typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()
#define MP make_pair

#define fst first
#define snd second

const LL INF = ULLONG_MAX / 4;

typedef vector< LL > VL;
typedef vector< VL > VVL;
typedef pair<int,int> PII;

class SkiResorts
{
public:
	long long minCost( vector <string> road, vector <int> altitude )
	{
		VI uniqalt( ALL( altitude ) );
		sort( ALL( uniqalt ) );
		uniqalt.erase( unique( ALL( uniqalt ) ), uniqalt.end() );

		const int V = road.size(), S = uniqalt.size();

		VVL distance( V, VL( S, INF ) );
		priority_queue< pair<LL,PII>, vector< pair<LL,PII> >, greater< pair<LL,PII> > > que;
		REP( i, 0, S )
		{
			LL d = abs( altitude[0] - uniqalt[i] );
			distance[0][i] = d;
			que.push( MP( d, MP( 0, i ) ) );
		}

		while ( !que.empty() )
		{
			int v = que.top().snd.fst;
			int s = que.top().snd.snd;
			LL d = que.top().fst;
			que.pop();
			
			REP( i, 0, V )
			{
				if ( road[v][i] == 'N' )
				{
					continue;
				}

				REP( j, 0, S )
				{
					LL nextdist = d + abs( altitude[i] - uniqalt[j] );
					if ( uniqalt[s] < uniqalt[j] || distance[i][j] <= nextdist )
					{
						continue;
					}
					distance[i][j] = nextdist;
					que.push( MP( nextdist, MP( i, j ) ) );
				}
			}
		}

		const LL res = *min_element( ALL( distance.back() ) );
		return res == INF ? -1 : res;
	}
};

コード（ FPSA ）

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

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

const LL INF = LLONG_MAX / 4;

typedef vector< LL > VL;
typedef vector< VL > VVL;

class SkiResorts
{
public:
	long long minCost( vector <string> road, vector <int> altitude )
	{
		VI uniqalt( ALL( altitude ) );
		sort( ALL( uniqalt ) );
		uniqalt.erase( unique( ALL( uniqalt ) ), uniqalt.end() );

		const int V = road.size(), S = uniqalt.size();

		VVL dist( V, VL( S, INF ) );
		queue< PII > que;
		vector< vector<bool> > inque( V, vector<bool>( S, false ) );
		REP( i, 0, S )
		{
			dist[0][i] = abs( altitude[0] - uniqalt[i] );
			que.push( MP( 0, i ) );
			inque[0][i] = true;
		}

		while ( !que.empty() )
		{
			PII cur = que.front();
			que.pop();
			inque[ cur.fst ][ cur.snd ] = false;

			REP( i, 0, V )
			{
				if ( road[ cur.fst ][i] == 'N' )
				{
					continue;
				}

				REP( j, 0, S )
				{
					LL d = dist[ cur.fst ][ cur.snd ] + abs( altitude[i] - uniqalt[j] );
					if ( uniqalt[ cur.snd ] < uniqalt[j] || dist[i][j] <= d )
					{
						continue;
					}
					dist[i][j] = d;
					if ( !inque[i][j] )
					{
						que.push( MP( i, j ) );
						inque[i][j] = true;
					}
				}
			}
		}

		LL res = *min_element( ALL( dist.back() ) );
		return res == INF ? -1 : res;
	}
};