結果

問題 No.1301 Strange Graph Shortest Path
ユーザー nok0
提出日時 2020-10-30 22:29:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,847 ms / 3,000 ms
コード長 1,824 bytes
コンパイル時間 488 ms
コンパイル使用メモリ 82,448 KB
実行使用メモリ 219,940 KB
最終ジャッジ日時 2024-09-13 00:28:07
合計ジャッジ時間 41,197 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import heapq
pop,push=heapq.heappop,heapq.heappush
class mincf:
	inf=2*10**18
	
	class E:
		def __init__(self,to,cap,cost,nx):
			self.to=to
			self.cap=cap
			self.cost=cost
			self.nx=nx
			self.rev=None
	
	def __init__(self, n):
		self.n=n
		self.head=[None]*n
		self.h=[0]*n
		self.d=[0]*n
		self.pre=[None]*n
	
	def ae(self,a,b,cap,cost):
		head=self.head
		head[a]=self.E(b,cap,cost,head[a])
		head[b]=self.E(a,0,-cost,head[b])
		head[a].rev=head[b]
		head[b].rev=head[a]
	
	def go(self,s,t,f):
		inf=self.inf
		n=self.n
		head=self.head
		h=self.h
		d=self.d
		pre=self.pre
		pq=[(0,s)]
		
		d[0]=0
		d[1:]=[inf]*(n-1)
		while pq:
			(a,v)=pop(pq)
			if d[v]<a:
				continue
			if v==t:
				break
			
			e=head[v]
			while e is not None:
				if e.cap>0:
					w=d[v]+e.cost+h[v]-h[e.to]
					if w<d[e.to]:
						d[e.to]=w
						push(pq,(w,e.to))
						pre[e.to]=e
				e=e.nx
		
		if d[t]==inf:
			return (0,0)
		
		for i in range(n):
			h[i]=min(h[i]+min(d[i],d[t]),inf)
		
		a=f
		v=t
		while v!=s:
			a=min(a,pre[v].cap)
			v=pre[v].rev.to
		v=t
		while v!=s:
			x=pre[v]
			y=x.rev
			x.cap-=a
			y.cap+=a
			v=y.to
		
		return (a,h[t])
	
	def calc(self,s,t,f=None):
		if f is None:
			f=self.inf
		amount=0
		cost=0
		while f>0:
			a,c=self.go(s,t,f)
			if a==0:
				break
			amount+=a
			f-=a
			cost+=a*c
		return (amount,cost)
		
n, m = map(int, input().split())
s, t, w = 0, n - 1, n
G = mincf(n + 2 * m)

def add(u, v, c, d):
    global w
    G.ae(u, w, 2, c)
    G.ae(w, v, 1, 0)
    G.ae(w, v, 1, d - c)
    w += 1

for i in range(m):
    u, v, c, d = map(int, input().split())
    u -= 1
    v -= 1
    add(u, v, c, d)
    add(v, u, c, d)

f,res = G.calc(s,t,2)
assert f == 2

print(res)
0