結果

問題 No.1301 Strange Graph Shortest Path
コンテスト
ユーザー marroncastle
提出日時 2020-11-29 20:21:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,722 bytes
コンパイル時間 266 ms
コンパイル使用メモリ 82,200 KB
実行使用メモリ 179,576 KB
最終ジャッジ日時 2024-09-13 02:08:18
合計ジャッジ時間 18,494 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 30 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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