ABC267E - Erasing Vertices 2

考え方

コスト最低の頂点から消す．
隣接頂点に対し，消した頂点の分のコストを修正してpushする．
（ダイクストラに似ている）

回答例

from heapq import heappop, heappush

N, M = map(int, input().split())
A = 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)

cost = [0] * N
for cur in range(N):
    for chi in G[cur]:
        cost[cur] += A[chi]

q = []
for i in range(N):
    heappush(q, (cost[i], i))

ans = 0
seen = [False] * N
while q:
    c, cur = heappop(q)
    if c > cost[cur]: continue
    if seen[cur]: continue
    seen[cur] = True
    ans = max(ans, c)
    for chi in G[cur]:
        if seen[chi]:continue
        cost[chi] -= A[cur]
        heappush(q, (cost[chi], chi))

print(ans)