[AtCoder] ABC 188 E – Peddler

2021年2月14日

問題

方針

町 \( i \) で売ることができる金の価格の最小値を \( d_i \) とします。\( d_i \) は \( \infty \) で初期化します。町 \( 1 \) から順番に調べていき、町 \( i \) から行くことができる町を \( j \) とすると、

\[ d_j \leftarrow \min(d_j, d_i, A_i)\]

と更新されます。得られる利益は、\( A_i – d_i \) と計算できます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int N, M;
    cin >> N >> M;
    int A[N], X[M], Y[M];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    vector<int> adj[N];
    for (int i = 0; i < M; i++) {
        cin >> X[i] >> Y[i];
        adj[X[i] - 1].push_back(Y[i] - 1);
    }
    int best = INT32_MIN;
    int d[N]{};
    fill(d, d + N, 2000000005);
    for (int i = 0; i < N - 1; i++) {
        for (int j : adj[i]) {
            d[j] = min(d[j], min(d[i], A[i]));
        }
    }
    for (int i = 1; i < N; i++) {
        best = max(best, A[i] - d[i]);
    }
    cout << best << "\n";
    return 0;
}