[AtCoder] ABC 188 E – Peddler
問題
方針
町 \( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません