結果
問題 | No.2604 Initial Motion |
ユーザー | titia |
提出日時 | 2024-01-12 23:18:31 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,171 bytes |
コンパイル時間 | 137 ms |
コンパイル使用メモリ | 81,572 KB |
実行使用メモリ | 583,960 KB |
最終ジャッジ日時 | 2024-01-12 23:19:06 |
合計ジャッジ時間 | 26,429 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
55,600 KB |
testcase_01 | AC | 41 ms
55,600 KB |
testcase_02 | AC | 59 ms
68,336 KB |
testcase_03 | AC | 2,255 ms
97,168 KB |
testcase_04 | AC | 2,061 ms
96,876 KB |
testcase_05 | AC | 2,166 ms
97,988 KB |
testcase_06 | AC | 1,939 ms
96,516 KB |
testcase_07 | AC | 1,911 ms
97,148 KB |
testcase_08 | AC | 2,295 ms
97,488 KB |
testcase_09 | AC | 1,969 ms
96,204 KB |
testcase_10 | AC | 2,656 ms
97,180 KB |
testcase_11 | AC | 2,042 ms
96,276 KB |
testcase_12 | AC | 2,117 ms
96,924 KB |
testcase_13 | MLE | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
ソースコード
import sys input = sys.stdin.readline from collections import Counter from heapq import heappop,heappush K,N,M=map(int,input().split()) A=list(map(int,input().split())) B=list(map(int,input().split())) E=[[] for i in range(N)] for i in range(M): u,v,d=map(int,input().split()) u-=1 v-=1 E[u].append((v,d)) E[v].append((u,d)) def dijkestra(fr): Q=[(0,fr)] DIS=[1<<61]*N DIS[fr]=0 while Q: dis,now=heappop(Q) if DIS[now]!=dis: continue for to,cost in E[now]: if DIS[to]>dis+cost: DIS[to]=dis+cost heappush(Q,(DIS[to],to)) return DIS # 最小費用流 # まず、グラフ作り V=N+N+2 # 頂点数 EDGE=[[] for i in range(V+1)] def add_edge(u,v,k,c): # u→vに容量k, 費用cの辺を張る X=[v,c,k,[]] Y=X[3]=[u,-c,0,X] EDGE[u].append(X) EDGE[v].append(Y) start=V-2 goal=V-1 C=Counter(A) for c in C: add_edge(start,c-1,C[c],0) DIS=dijkestra(c-1) for j in range(N): add_edge(c-1,N+j,K,DIS[j]) for i in range(N): add_edge(N+i,goal,B[i],0) #print(EDGE) Flowed_edge=[[] for i in range(V)] BACK=[-1]*(V) P=[0]*(V) # ポテンシャル LA=0 # 最終的な答え for fl in range(K): ANS=[1<<62]*V Q=[start] # 一次元化している。(time<<20)+node ANS[start]=0 while Q: # ここはダイクストラ x = heappop(Q) time = x>>20 fr = x - (time<<20) if time > ANS[fr]: continue for to,cost,vol,f_edge in EDGE[fr]: if vol>0 and ANS[to]>ANS[fr]+cost+P[fr]-P[to]:# ポテンシャルによりコストを調整 ANS[to]=ANS[fr]+cost+P[fr]-P[to] BACK[to]=fr Flowed_edge[to]=f_edge heappush(Q,((ANS[to])<<20)+to) LA+=ANS[goal]+P[goal] P=[P[i]+ANS[i] for i in range(V)] # ポテンシャルを調整 NOW=goal while NOW!=start: f_edge=Flowed_edge[NOW] f_edge[3][2]-=1 # 流した分の容量を削る f_edge[2]+=1 # 逆向きに+1する NOW=BACK[NOW] print(LA)