結果

問題 No.1301 Strange Graph Shortest Path
ユーザー rlangevin
提出日時 2023-10-20 00:11:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,918 bytes
コンパイル時間 150 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 182,956 KB
最終ジャッジ日時 2024-09-19 20:05:24
合計ジャッジ時間 17,183 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 30 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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

import sys
input = sys.stdin.readline
# https://tjkendev.github.io/procon-library/python/min_cost_flow/primal-dual.html
# (minimum cost flow)
class MinCostFlow:
def __init__(self, n):
self.n = n
self.G = [[] for i in range(n)]
def addEdge(self, f, t, cap, cost):
# [to, cap, cost, rev]
self.G[f].append([t, cap, cost, len(self.G[t])])
self.G[t].append([f, 0, -cost, len(self.G[f])-1])
def minCostFlow(self, s, t, f):
n = self.n
G = self.G
prevv = [0]*n; preve = [0]*n
INF = 10**9+7
res = 0
while f:
dist = [INF]*n
dist[s] = 0
update = 1
while update:
update = 0
for v in range(n):
if dist[v] == INF:
continue
gv = G[v]
for i in range(len(gv)):
to, cap, cost, rev = gv[i]
if cap > 0 and dist[v] + cost < dist[to]:
dist[to] = dist[v] + cost
prevv[to] = v; preve[to] = i
update = 1
if dist[t] == INF:
return -1
d = f; v = t
while v != s:
d = min(d, G[prevv[v]][preve[v]][1])
v = prevv[v]
f -= d
res += d * dist[t]
v = t
while v != s:
e = G[prevv[v]][preve[v]]
e[1] -= d
G[v][e[3]][1] += d
v = prevv[v]
return res
N, M = map(int, input().split())
G = MinCostFlow(N)
for i in range(M):
u, v, c, d = map(int, input().split())
u, v = u - 1, v - 1
G.addEdge(u, v, 1, c)
G.addEdge(u, v, 1, d)
G.addEdge(v, u, 1, c)
G.addEdge(v, u, 1, d)
print(G.minCostFlow(0, N-1, 2))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0