結果

問題 No.1301 Strange Graph Shortest Path
ユーザー marroncastlemarroncastle
提出日時 2020-11-29 20:21:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,722 bytes
コンパイル時間 416 ms
コンパイル使用メモリ 87,244 KB
実行使用メモリ 188,552 KB
最終ジャッジ日時 2023-10-11 02:36:19
合計ジャッジ時間 19,832 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
71,620 KB
testcase_01 AC 70 ms
71,476 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 72 ms
71,340 KB
testcase_33 AC 467 ms
176,588 KB
testcase_34 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 最小費用流(minimum cost flow) BellmanFord O(FEV)
class MinCostFlow:
  def __init__(self, n):
    self.n = n
    self.G = [[] for i in range(n)]

  def add_edge(self, f, t, cap, cost):
    # [to, cap, cost, rev]
    self.G[f].append([t, cap, 0, cost, len(self.G[t])])
    self.G[t].append([f, 0, 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, flow, 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
        if G[v][e[4]][2]==0:
          e[2] += d
        else:
          G[v][e[4]][2] -= d
        G[v][e[4]][1] += d
        v = prevv[v]
    return res

import sys,os,io
input = sys.stdin.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n, m = map(int, input().split())
graph = MinCostFlow(n)
for i in range(m):
  u, v, c, d = map(int, input().split())
  graph.add_edge(u-1, v-1, 1, c)
  graph.add_edge(v-1, u-1, 1, c)
  graph.add_edge(u-1, v-1, 1, d)
  graph.add_edge(v-1, u-1, 1, d)
print(graph.minCostFlow(0, n-1, 2))
0