atcoder abc188 E - Peddler

問題

N個の町がある。町を結ぶM本の道がある。それぞれの道は $ X_i $ から $ Y_i $ への一方通行になっている。

$ 町_i $ では $ A_i $ 円の金(gold)を買ったり売ったりできる。

ある町で金を買い、いくつかの道を使った後、買った町とは別の町で金を売ったとき、利益(金を売った価格-金を買った価格)の最大値を求める。

解法

DAG (Directed Acyclic Graph/閉路を含まない有向グラフ) であることがわかるため、DPで解ける

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
const int INF = 1e9;

int n,m;
vector<int> a,x,y;
vector<int> dp; // dp[i]: 街iに到達できる街(街i自身を含まない)における金の最安値

void solve() {
  dp.resize(n,INF*2); // 十分大きい値で初期化
  vector<vector<int>> g(n); 

  REP(i,m) g[x[i]].push_back(y[i]); // 有向グラフ

  REP(i,n) {
    for(auto v: g[i]) {
      dp[v] = min(min(dp[i],dp[v]), a[i]);
    }
  }

  int ans = -INF;
  REP(i,n) ans = max(ans, a[i]-dp[i]); // max(ans, 街iの金の売値 - 街iに到達できる金の最安値)

  cout << ans << endl;
  return;
}

int main() {
  cin >> n >> m;
  a.resize(n);
  REP(i,n) cin >> a[i];
  x.resize(m); y.resize(m);
  REP(i,m) {
    cin >> x[i] >> y[i];
    x[i]--; y[i]--;
  }

  solve();
  return 0;
}