結果
| 問題 | No.1301 Strange Graph Shortest Path |
| ユーザー |
 Kite_kuma
|
| 提出日時 | 2020-10-30 21:27:51 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 5,176 bytes |
| コンパイル時間 | 1,071 ms |
| コンパイル使用メモリ | 82,120 KB |
| 実行使用メモリ | 302,304 KB |
| 最終ジャッジ日時 | 2024-09-13 00:21:21 |
| 合計ジャッジ時間 | 44,178 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 39 ms
53,876 KB |
| testcase_01 | AC | 40 ms
53,552 KB |
| testcase_02 | AC | 1,529 ms
290,372 KB |
| testcase_03 | AC | 1,391 ms
271,200 KB |
| testcase_04 | RE | - |
| testcase_05 | AC | 1,342 ms
291,696 KB |
| testcase_06 | RE | - |
| testcase_07 | AC | 1,749 ms
286,340 KB |
| testcase_08 | AC | 1,357 ms
270,628 KB |
| testcase_09 | AC | 1,313 ms
272,412 KB |
| testcase_10 | AC | 1,233 ms
268,296 KB |
| testcase_11 | RE | - |
| testcase_12 | AC | 1,666 ms
291,856 KB |
| testcase_13 | AC | 1,461 ms
291,700 KB |
| testcase_14 | RE | - |
| testcase_15 | AC | 1,348 ms
272,644 KB |
| testcase_16 | RE | - |
| testcase_17 | AC | 1,813 ms
296,556 KB |
| testcase_18 | AC | 1,741 ms
279,928 KB |
| testcase_19 | AC | 1,405 ms
287,508 KB |
| testcase_20 | RE | - |
| testcase_21 | AC | 1,572 ms
291,960 KB |
| testcase_22 | RE | - |
| testcase_23 | AC | 1,352 ms
293,612 KB |
| testcase_24 | RE | - |
| testcase_25 | AC | 1,762 ms
300,140 KB |
| testcase_26 | AC | 1,624 ms
287,324 KB |
| testcase_27 | AC | 1,355 ms
290,480 KB |
| testcase_28 | AC | 1,299 ms
283,600 KB |
| testcase_29 | RE | - |
| testcase_30 | RE | - |
| testcase_31 | RE | - |
| testcase_32 | AC | 39 ms
54,576 KB |
| testcase_33 | AC | 896 ms
293,108 KB |
| testcase_34 | AC | 1,477 ms
287,176 KB |
ソースコード
import sys
import heapq
input = sys.stdin.readline
BIG = 10 ** 9
class mcf_graph_int_cost:
"""
頂点数、及び、costの総和が、4294967295 (== (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):
self.dist = [4294967295] * self.n
self.pv = [-1] * self.n
self.pe = [-1] * self.n
self.vis = [False] * self.n
que = [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():
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, K = map(int, input().split())
# g = mcf_graph_int_cost(2 * N + 2)
# s = 2 * N
# t = 2 * N + 1
# g.add_edge(s, t, N * K, BIG)
# for i in range(N):
# g.add_edge(s, i, K, 0)
# g.add_edge(N + i, t, K, 0)
# for i in range(N):
# As = map(int, input().split())
# for j, A in enumerate(As):
# g.add_edge(i, N + j, 1, BIG - A)
# result = g.flow(s, t, N * K)
# print(N * K * BIG - result[1])
# grid = [['.' for _ in range(N)] for _ in range(N)]
# edges = g.edges()
# for e in edges:
# if e.from_ == s or e.to == t or e.flow == 0:
# continue
# grid[e.from_][e.to - N] = 'X'
# for row in grid:
# print(''.join(row))
n, m = map(int, input().split())
s, t = 0, n - 1
graph = mcf_graph_int_cost(n + m)
for i in range(m):
u, v, c, d = map(int, input().split())
assert 1 <= u <= n and 1 <= v <= n and c <= d
u -= 1
v -= 1
mid = n + i
graph.add_edge(u, mid, 2, c)
graph.add_edge(mid, v, 1, 0)
graph.add_edge(mid, v, 1, d - c)
graph.add_edge(v, mid, 2, c)
graph.add_edge(mid, u, 1, 0)
graph.add_edge(mid, u, 1, d - c)
flow, cost = graph.flow(s, t, 2)
assert flow == 2
print(cost)