結果
問題 | No.2573 moving up |
ユーザー |
👑 ![]() |
提出日時 | 2023-12-01 08:56:50 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,904 bytes |
コンパイル時間 | 464 ms |
コンパイル使用メモリ | 82,240 KB |
実行使用メモリ | 186,384 KB |
最終ジャッジ日時 | 2024-09-26 15:13:18 |
合計ジャッジ時間 | 21,433 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 31 |
ソースコード
# Primal-Dual: https://tjkendev.github.io/procon-library/python/min_cost_flow/primal-dual.htmlfrom heapq import heappush, heappopfrom collections import dequeclass MinCostFlow:INF = 10**18def __init__(self, N):self.N = Nself.G = [[] for i in range(N)]def add_edge(self, fr, to, cap, cost):forward = [to, cap, cost, None]backward = forward[3] = [fr, 0, -cost, forward]self.G[fr].append(forward)self.G[to].append(backward)def flow(self, s, t, f):N = self.NG = self.GINF = MinCostFlow.INFres = 0H = [0]*Nprv_v = [0]*Nprv_e = [None]*Nd0 = [INF]*Ndist = [INF]*Nwhile f:dist[:] = d0dist[s] = 0que = [(0, s)]while que:c, v = heappop(que)if dist[v] < c:continuer0 = dist[v] + H[v]for e in G[v]:w, cap, cost, _ = eif cap > 0 and r0 + cost - H[w] < dist[w]:dist[w] = r = r0 + cost - H[w]prv_v[w] = vprv_e[w] = eheappush(que, (r, w))if dist[t] == INF:return Nonefor i in range(N):H[i] += dist[i]d = fv = twhile v != s:d = min(d, prv_e[v][1])v = prv_v[v]f -= dres += d * H[t]v = twhile v != s:e = prv_e[v]e[1] -= de[3][1] += dv = prv_v[v]return resINF = 10 ** 17 + 1H, W = map(int, input().split())dists = [[INF for _ in range(W)] for _ in range(W)]dist = [[INF for _ in range(H + W)] for _ in range(H)]dq = deque()dx = [-1, -1, 0, 0, 1, 1]dy = [-1, 0, -1, 1, 0, 1]for i in range(W):x, y = map(int, input().split())for j in range(H):for k in range(H + W):dist[j][k] = INFdist[x - 1][y - 1] = 0dq.append([x - 1, y - 1])while len(dq):px, py = dq.popleft()for j in range(6):if px + dx[j] >= 0 and px + dx[j] < H and py + dy[j] >= 0 and py + dy[j] < px + dx[j] + W:if dist[px + dx[j]][py + dy[j]] < INF:continuedist[px + dx[j]][py + dy[j]] = dist[px][py] + 1dq.append([px + dx[j], py + dy[j]])for j in range(W):dists[i][j] = dist[0][j]'''graph = MinCostFlow(2 * W + 2)for i in range(W):graph.add_edge(2 * W, i, 1, 0)graph.add_edge(W + i, 2 * W + 1, 1, 0)for i in range(W):for j in range(W):graph.add_edge(i, W + j, 1, dists[i][j])ans = graph.flow(2 * W, 2 * W + 1, W)print(ans)'''print(0)