ABC237E

ABC237E の解説

atcoder.jp

解答コード

https://atcoder.jp/contests/abc237/submissions/28967250

問題

ABC237E_overview

移動する際に発生するコストが最大となるルートを探す問題です．

解説

幅優先探索を用いて，全ての地点に移動した後，どの地点で終了した方が最もコストが大きくなるか探します．

最終的に得られるリストのイメージは，上図（例１）の場合，
[0, 2, -4, 3]
となります．

リストの4番目（ゼロインデックスで3番目）の数字が3であるのは，
地点1から地点4まで適切なルートで移動した場合，コスト（楽しさ）が3であることを示しています．

この際，どんなルートで移動したら良いかといった具体的な道順は，保存していません．

実装します．

幅優先探索を行うので，dequeを使います．

from collections import deque

標準入力を読み込みます．
地点を示す番号は，ゼロインデックスで処理します．

N, M = map(int, input().split())
H = list(map(int, input().split()))

G = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(lambda x: int(x)-1, input().split())
    G[u].append(v)
    G[v].append(u)

幅優先探索をしながら，コストの計算を書くと煩雑になるので，
あらかじめ高低差に応じて楽しさを計算する関数を作ります．

def calc_cost(hs, he):
    if hs >= he:
        return hs-he
    else:
        return 2*(hs-he)

地点0から処理を開始します．各地点の初期値は-infにします．

x = 0
costs = [float('-inf')]*N
costs[x] = 0
dq = deque([0])

幅優先探索を実行します．
ルートを探索する条件は，以前のルートでその地点に来た時のコストの最大値を，今回移動して来たことでコストの最大値を更新できるかどうかになります．

最後にコストの最大値を出力すると終了です．

while dq:
    x_now = dq.popleft()
    cost_now = costs[x_now]

    for x_next in G[x_now]:
        # 以前の他のルートでその地点に来た時の最大値
        cost_next = costs[x_next]
        # 今回移動して来たときのコストの計算値
        cost_calced = cost_now + calc_cost(H[x_now], H[x_next])
        if cost_calced > cost_next:
            costs[x_next] = cost_calced
            dq.append(x_next)
print(max(costs))

以上，ABC237Eの解法でした．