結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import sysinput = 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 = nself.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.nG = self.Gprevv = [0]*n; preve = [0]*nINF = 10**9+7res = 0while f:dist = [INF]*ndist[s] = 0update = 1while update:update = 0for v in range(n):if dist[v] == INF:continuegv = 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] + costprevv[to] = v; preve[to] = iupdate = 1if dist[t] == INF:return -1d = f; v = twhile v != s:d = min(d, G[prevv[v]][preve[v]][1])v = prevv[v]f -= dres += d * dist[t]v = twhile v != s:e = G[prevv[v]][preve[v]]e[1] -= dG[v][e[3]][1] += dv = prevv[v]return resN, 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 - 1G.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))