結果

問題 No.1301 Strange Graph Shortest Path
ユーザー nok0nok0
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
53,136 KB
testcase_01 AC 42 ms
54,800 KB
testcase_02 AC 1,112 ms
214,036 KB
testcase_03 AC 991 ms
196,204 KB
testcase_04 AC 1,522 ms
215,400 KB
testcase_05 AC 1,122 ms
215,068 KB
testcase_06 AC 1,414 ms
207,676 KB
testcase_07 AC 1,234 ms
209,160 KB
testcase_08 AC 1,085 ms
197,876 KB
testcase_09 AC 981 ms
193,244 KB
testcase_10 AC 946 ms
195,688 KB
testcase_11 AC 1,164 ms
205,788 KB
testcase_12 AC 1,175 ms
205,120 KB
testcase_13 AC 1,032 ms
209,256 KB
testcase_14 AC 1,595 ms
202,904 KB
testcase_15 AC 1,024 ms
196,544 KB
testcase_16 AC 1,392 ms
211,980 KB
testcase_17 AC 1,212 ms
216,768 KB
testcase_18 AC 1,255 ms
205,364 KB
testcase_19 AC 985 ms
199,416 KB
testcase_20 AC 1,351 ms
200,856 KB
testcase_21 AC 1,250 ms
211,804 KB
testcase_22 AC 1,584 ms
206,712 KB
testcase_23 AC 999 ms
209,628 KB
testcase_24 AC 1,612 ms
204,876 KB
testcase_25 AC 1,360 ms
213,236 KB
testcase_26 AC 1,265 ms
207,024 KB
testcase_27 AC 988 ms
203,052 KB
testcase_28 AC 991 ms
207,396 KB
testcase_29 AC 1,847 ms
214,464 KB
testcase_30 AC 1,020 ms
209,372 KB
testcase_31 AC 1,245 ms
211,172 KB
testcase_32 AC 42 ms
53,632 KB
testcase_33 AC 964 ms
207,980 KB
testcase_34 AC 1,094 ms
219,940 KB
権限があれば一括ダウンロードができます

ソースコード

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