WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
}