Codeforces #182 Div2 D "Yaroslav and Time"
問題
http://codeforces.com/contest/302/problem/D
訳
ヤロスラフは"Time"というゲームで遊んでいる。
このゲームは彼のあとどのくらい生きるか、というタイマーが表示されている。
このタイマーが0を表示した瞬間、プレイヤーキャラは死に、ゲームオーバーとなる。
このゲームにはn個のクロックステーションがあり、
i番目のステーションは、平面上の(x_i, y_i)の位置にある。
プレイヤーがi番目のステーションに到着すると、タイマーがa_iだけ加算される。
このステーションは1回しか使用できないので、もし2回目以降に訪れた場合、
タイマーは加算されない。
プレイヤーは2つのステーション間の移動に、
distを2つのステーションの距離、dを単位距離あたりにかかる時間としたときに、
d * distだけ時間を費やさなければならない。
i番目とj番目のステーションの距離は、
| x_i - x_j | + | y_i - y_j |と定義される。
最初、プレイヤーは1番目のステーションにおり、タイマーは0となっている。
1番目のステーションにて、単位時間を1円で買ってから出発する。
ヤロスラフは、n番目のステーションにたどり着くために、
最初にどのくらい時間を買えばいいのかを考えている。
n番目のステーションにたどり着くため、使わなくてはいけない最小の金額を出力せよ。
制約
3 <= n <= 100
10^3 <= d <= 10^5
1 <= a_i <= 10^3
-100 <= x_i, y_i <= 100
考えた事
ステーションを頂点、かかる時間をコストとしたときの
1からNへの最短経路を求めればよい。
ステーションiからjに移動した時に、
制約により、残り時間が増えていることはないため、
負の閉路は存在しない。
ステーションiからjへのコストは、iでa_iだけ時間が回復しているため、
d * dist - a_iとなる。
事後
i j kが・・・
i j kがぁぁぁぁぁぁぁぁ!!!
for( int i = 0; i < N; k++ ){ for( int j = 0; j < N; j++ ){ for( int k = 0; k < N; k++ ){ G[i][j] = min( G[i][j], G[i][k] + G[k][j] ); } } }
ソースコード
typedef long long ll; int N, D; int A[110]; ll G[110][110]; int X[110], Y[110]; int main() { cin >> N >> D; for( int i = 1; i < N - 1; i++ ){ cin >> A[i]; } A[0] = A[N-1] = 0; for( int i = 0; i < N; i++ ){ cin >> X[i] >> Y[i]; } // グラフ作成 for( int i = 0; i < N; i++ ){ for( int j = 0; j < N; j++ ){ ll dist = abs( X[i] - X[j] ) + abs( Y[i] - Y[j] ); if( i == j ){ G[i][j] = 0; }else{ // i -> j G[i][j] = dist * D - A[i]; } } } // ワーシャルフロイド 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] ); } } } cout << G[0][N-1] << endl; }