ABC188E - Peddler

解法1

考え方

頂点を大きい方から見ていけば，「各街から到達できる街での最高値」がわかる．
求めたい答えは，「(街$i$から到達できる街での最高値) - (街$i$での購入価格)」．

回答例

N, M = map(int, input().split())
A = list(map(int, input().split()))
G = [[] for _ in range(N)]
inv = [[] for _ in range(N)]
for _ in range(M):
  X, Y = map(lambda x: int(x) - 1, input().split())
  G[X].append(Y)
  inv[Y].append(X)

ans = - 1 << 60
highest = [a for a in A]
for cur in range(N - 1, -1, -1):
  for par in inv[cur]:
    highest[par] = max(highest[par], highest[cur])
  for chi in G[cur]:
    ans = max(ans, highest[chi] - A[cur])

print(ans)

解法2：BFS

考え方

Editorial - AtCoder Beginner Contest 188

回答例

from collections import deque

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = sorted([(a, i) for i, a in enumerate(A)])
G = [[] for _ in range(N)]
for _ in range(M):
  X, Y = map(lambda x: int(x) - 1, input().split())
  G[X].append(Y)

seen = [False] * N
ans = -1 << 60
for a, i in B:
  q = deque([i])
  while q:
    cur = q.popleft()
    for chi in G[cur]:
      if seen[chi]: continue
      ans = max(ans, A[chi] - a)
      q.append(chi)
      seen[chi] = True

print(ans)