概要
XY 平面上に N 個の点があり、最初 1 番( 1-indexed )の点にいて、n 番の点に移動したい。
点から点に移動するとき、そのマンハッタン距離 * d の費用がかかる。
1 番と n 番以外の点では、 だけ費用を補充できる。
最初に持っていなければならない費用の最小値を求めよ。
解法
点を頂点としたグラフを考えます。(このグラフは完全グラフになります)
辺 ( u, v ) のコストは、u で補給をして v に移動するときの消費費用であると考え、 とします。
と 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; }