PAST5I
初回考察
標高の高い方から低い方へしか動けない
有向グラフ
ゴールがたくさん
コスト0の辺で束ねる？
各ゴールからone to allのダイクストラ法？
後者をやって、ダメなら前者にしよう
考察完了
実装
どうせダイクストラ法やるなら前者の実装をする追加工数は大したことないので後者をやるメリットはないなと判断
前者の実装をする追加コード :
(1) AC
pythondef solve(N, M, K, HS, CS, ABS):
from collections import defaultdict
edges = defaultdict(dict)
for i in range(M):
frm, to = ABS[i]
frm -= 1
to -= 1
if HS[frm] < HS[to]:
to, frm = frm, to
# reversed edge
edges[to][frm] = 1
goal = N
for c in CS:
edges[goal][c - 1] = 0 # (1)
distances = one_to_all(goal, N + 1, edges)
INF = 9223372036854775807
for i in range(N):
d = distances[i]
if d == INF:
d = -1
print(d)Related Pages
- →chokudai×貪欲法の証明パターン×選択肢が少ない方から貪欲×マトロイド×クラスカル法×区間スケジューリング×交換しても悪化しない×アルゴリズムとデータ構造×区間はマトロイドではない×abc076b×現在が良いほど未来も良い×poj3617×poj3069×ダイクストラ法×agc009a×arc111×abc187×arc110c×一回り小さい同じ形の問題×agc049b×abc103d×abc023d×和の比率の最大化×単位時間ジョブスケジューリング問題×乱択＋貪欲×abc171_f×離散凸性→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]