torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

Codeforces #182, Division 2, D : Yaroslav and Time

概要

XY 平面上に N 個の点があり、最初 1 番( 1-indexed )の点にいて、n 番の点に移動したい。
点から点に移動するとき、そのマンハッタン距離 * d の費用がかかる。
1 番と n 番以外の点では、a_i だけ費用を補充できる。
最初に持っていなければならない費用の最小値を求めよ。

解法

点を頂点としたグラフを考えます。(このグラフは完全グラフになります)
辺 ( u, v ) のコストは、u で補給をして v に移動するときの消費費用であると考え、( |x_u - x_v| + | y_u - y_v | ) * d とします。
a_i と d の制約から、このグラフに負閉路はできません。
従って、このグラフの最短経路問題を解くことで答えが求まります。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

const int INF = INT_MAX / 2;

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, d;
	cin >> n >> d;

	VI as( n, 0 );
	REP( i, 1, n - 1 )
	{
		cin >> as[i];
	}

	VI xs( n ), ys( n );
	REP( i, 0, n )
	{
		cin >> xs[i] >> ys[i];
	}

	VVI G( n, VI( n, INF ) );
	REP( i, 0, n )
	{
		G[i][i] = 0;
	}

	REP( i, 0, n )
	{
		REP( j, 0, n )
		{
			if ( i == j )
			{
				continue;
			}

			int cost = ( abs( xs[i] - xs[j] ) + abs( ys[i] - ys[j] ) ) * d;
			int need = cost - as[i];
			G[i][j] = need;
		}
	}

	REP( k, 0, n )
	{
		REP( i, 0, n )
		{
			REP( j, 0, n )
			{
				G[i][j] = min( G[i][j], G[i][k] + G[k][j] );
			}
		}
	}

	cout << G[0][ n - 1 ] << endl;

	return 0;
}