結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー |
|
提出日時 | 2020-11-27 21:25:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,189 ms / 3,000 ms |
コード長 | 1,892 bytes |
コンパイル時間 | 372 ms |
コンパイル使用メモリ | 82,340 KB |
実行使用メモリ | 210,488 KB |
最終ジャッジ日時 | 2024-09-13 00:50:13 |
合計ジャッジ時間 | 35,269 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
import randomfrom heapq import heappush, heappopclass 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.N; G = 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] = v; prv_e[w] = eheappush(que, (r, w))if dist[t] == INF:return Nonefor i in range(N):H[i] += dist[i]d = f; v = 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 resimport sysinput = sys.stdin.readlineN,M = map(int,input().split())G = MinCostFlow(N)for _ in range(M):u,v,c,d = map(int,input().split())G.add_edge(u-1,v-1,1,c)G.add_edge(u-1,v-1,1,d)G.add_edge(v-1,u-1,1,c)G.add_edge(v-1,u-1,1,d)print(G.flow(0,N-1,2))