結果

問題 No.1301 Strange Graph Shortest Path
ユーザー zkouzkou
提出日時 2020-11-07 10:43:37
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,474 bytes
コンパイル時間 451 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 309,604 KB
最終ジャッジ日時 2024-09-13 00:38:56
合計ジャッジ時間 50,924 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
54,852 KB
testcase_01 AC 41 ms
54,624 KB
testcase_02 AC 1,910 ms
298,880 KB
testcase_03 AC 1,687 ms
269,148 KB
testcase_04 WA -
testcase_05 AC 1,766 ms
298,688 KB
testcase_06 WA -
testcase_07 AC 2,094 ms
293,976 KB
testcase_08 AC 1,732 ms
270,836 KB
testcase_09 AC 1,539 ms
280,012 KB
testcase_10 AC 1,509 ms
272,004 KB
testcase_11 WA -
testcase_12 AC 1,824 ms
299,600 KB
testcase_13 AC 1,734 ms
300,064 KB
testcase_14 WA -
testcase_15 AC 1,507 ms
280,732 KB
testcase_16 WA -
testcase_17 AC 2,188 ms
303,552 KB
testcase_18 AC 2,103 ms
287,824 KB
testcase_19 AC 1,574 ms
295,484 KB
testcase_20 WA -
testcase_21 AC 1,926 ms
300,792 KB
testcase_22 WA -
testcase_23 AC 1,705 ms
301,508 KB
testcase_24 WA -
testcase_25 AC 2,023 ms
307,440 KB
testcase_26 AC 1,967 ms
295,208 KB
testcase_27 AC 1,641 ms
297,876 KB
testcase_28 AC 1,642 ms
290,916 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 41 ms
54,128 KB
testcase_33 AC 1,173 ms
303,064 KB
testcase_34 AC 1,729 ms
289,580 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
import heapq
input = sys.stdin.readline
class mcf_graph_int_cost:
"""
cost4294967295 (== (1 << 32) - 1)
"""
def __init__(self, n):
self.n = n
self.pos = []
self.g = [[] for _ in range(n)]
def add_edge(self, from_, to, cap, cost):
# assert 0 <= from_ < self.n
# assert 0 <= to < self.n
m = len(self.pos)
self.pos.append((from_, len(self.g[from_])))
self.g[from_].append(self.__class__._edge(to, len(self.g[to]), cap, cost))
self.g[to].append(self.__class__._edge(from_, len(self.g[from_]) - 1, 0, -cost))
return m
class edge:
def __init__(self, from_, to, cap, flow, cost):
self.from_ = from_
self.to = to
self.cap = cap
self.flow = flow
self.cost = cost
def get_edge(self, i):
_e = self.g[self.pos[i][0]][self.pos[i][1]]
_re = self.g[_e.to][_e.rev]
return self.__class__.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost)
def edges(self):
ret = []
for i in range(len(self.pos)):
_e = self.g[self.pos[i][0]][self.pos[i][1]]
_re = self.g[_e.to][_e.rev]
ret.append(self.__class__.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost))
return ret
def _dual_ref(self, s, t):
self.dist = [4294967295] * self.n
self.pv = [-1] * self.n
self.pe = [-1] * self.n
self.vis = [False] * self.n
que = [s] # s == (0 << 32) + s
self.dist[s] = 0
while que:
v = heapq.heappop(que) & 4294967295
if self.vis[v]:
continue
self.vis[v] = True
if v == t:
break
for i in range(len(self.g[v])):
e = self.g[v][i]
if self.vis[e.to] or e.cap == 0:
continue
cost = e.cost - self.dual[e.to] + self.dual[v]
if self.dist[e.to] > self.dist[v] + cost:
self.dist[e.to] = self.dist[v] + cost
self.pv[e.to] = v
self.pe[e.to] = i
heapq.heappush(que, ((self.dist[e.to] << 32) + e.to))
if not self.vis[t]:
return False
for v in range(self.n):
if not self.vis[v]:
continue
self.dual[v] -= self.dist[t] - self.dist[v]
return True
def slope(self, s, t, flow_limit=4294967295):
# assert 0 <= s < self.n
# assert 0 <= t < self.n
# assert s != t
self.dual = [0] * self.n
self.dist = [4294967295] * self.n
self.pv = [-1] * self.n
self.pe = [-1] * self.n
self.vis = [False] * self.n
flow = 0
cost = 0
prev_cost = -1
result = [(flow, cost)]
while flow < flow_limit:
if not self._dual_ref(s, t):
break
c = flow_limit - flow
v = t
while v != s:
c = min(c, self.g[self.pv[v]][self.pe[v]].cap)
v = self.pv[v]
v = t
while v != s:
e = self.g[self.pv[v]][self.pe[v]]
e.cap -= c
self.g[v][e.rev].cap += c
v = self.pv[v]
d = -self.dual[s]
flow += c
cost += c * d
if prev_cost == d:
result.pop()
result.append((flow, cost))
prev_cost = cost
return result
def flow(self, s, t, flow_limit=4294967295):
return self.slope(s, t, flow_limit)[-1]
class _edge:
def __init__(self, to, rev, cap, cost):
self.to = to
self.rev = rev
self.cap = cap
self.cost = cost
N, M = map(int, input().split())
g = mcf_graph_int_cost(N + 2 * M)
for i in range(M):
u, v, c, d = map(int, input().split())
u -= 1
v -= 1
# c
u2 = N + i
v2 = N + M + i
g.add_edge(u, u2, 2, 0)
g.add_edge(v, u2, 2, 0)
g.add_edge(u2, v2, 1, c)
g.add_edge(u2, v2, 1, d)
g.add_edge(v2, u, 2, 0)
g.add_edge(v2, v, 2, 0)
print(g.flow(0, N - 1, 2)[1])
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0