ABC237E - Skiing

「スコアの符号を変えればダイクストラが使える！」と思って嘘解法で通してしまいました．．．

負の辺を含まない形に問題を修正しなければなりません．
Editorial - AtCoder Beginner Contest 237

考え方

符号の反転

もし，スコア反転後に負辺がなければ，「スコアの符号を反転させて，最短経路（最小コストの経路）の問題を解き，最小コストに$-1$をかけたものが答え」となる．これは，ダイクストラ法が使える．

しかし，符号を反転させたあとのコストは，

\begin{aligned}
&\mathrm{cost_{1}}(X, Y) \\
&=
\begin{cases}
\, - (H_{X} - H_{Y}) < 0 & (H_{X} > H_{Y})\\
\, -2 (H_{X} - H_{Y}) \geq 0 & (H_{X} \leq H_{Y})\\
\end{cases}
\end{aligned}

となっている．そのため，このままではダイクストラ法が使えない．

そこで，コストをすべて正にするような変換が必要となる．

ポテンシャルの導入

さて，新しいコスト

\begin{aligned}
\mathrm{cost_{2}}(X, Y)
&= \mathrm{cost_{1}}(X, Y) + p_{X} - p_{Y}
\end{aligned}

を考える．ここで，$p_{X}$は，各頂点$X$ごとに決めた任意定数である．

すると，スタート地点$S$からゴール地点$G$までの合計コストは，経路を辺の集合$E$で表すとき

\begin{aligned}
&\sum_{(x, y) \in E} \mathrm{cost_{2}}(x, y) \\
&= \sum_{(x, y) \in E} \mathrm{cost_{1}}(x, y) +
+\sum_{(x, y) \in E} ( p_{x} - p_{y}) \\
&= \sum_{(x, y) \in E} \mathrm{cost_{1}}(x, y)
+ p_{S} - p_{G}
\end{aligned}

となる．

今求めたいのは，$\sum_{(x, y) \in E} \mathrm{cost_{1}}(x, y)$であるが，$\sum_{(x, y) \in E} \mathrm{cost_{2}}(x, y)$を求めて最後に定数$p_{S} - p_{G}$の分だけ補正すれば，$\mathrm{cost_{2}}(X, Y) $に置き換えた問題を考えて良いことになる．

解くべき問題

今回の場合は，$p_{X} = H_{X}$というポテンシャルの導入で，負の辺をなくすことができる：

\begin{aligned}
&\mathrm{cost_{2}}(X, Y) \\
&= \mathrm{cost_{1}} (X, Y) + (H_{X} - H_{Y}) \\
&=
\begin{cases}
\, 0 & (H_{X} > H_{Y})\\
\, -( H_{X} - H_{Y} ) \geq 0 & (H_{X} \leq H_{Y})\\
\end{cases}
\end{aligned}

以上より，

1. すべての頂点$Y$に対して$\mathrm{cost_{2}}(X=1, Y) $を計算し，
2. $(-1) \times \min\{ \mathrm{cost_{1}} (X=1, Y)\,|\, Y = 1,2,...\}$ を答えとして出力する

とすればよい．

【参考】【解説 実況】ABC237 E問題【かつっぱ】 - YouTube

回答例

import heapq

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

INF = 1 << 60
dist = [INF] * N
dist[0] = 0
q = [(0, 0)]
while q:
  d, cur = heapq.heappop(q)
  if dist[cur] < d:
    continue
  for chi in G[cur]:
    new = d
    if H[cur] < H[chi]:
      new += -(H[cur] - H[chi])
    if new < dist[chi] :
      dist[chi] = new
      heapq.heappush(q, (dist[chi], chi))
      
print(- min(dist[i] - H[0] + H[i] for i in range(N)))