結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー | navel_tos |
提出日時 | 2023-05-16 23:39:40 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,994 bytes |
コンパイル時間 | 250 ms |
コンパイル使用メモリ | 82,372 KB |
実行使用メモリ | 200,004 KB |
最終ジャッジ日時 | 2024-05-08 16:05:06 |
合計ジャッジ時間 | 11,530 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
61,932 KB |
testcase_01 | AC | 38 ms
52,932 KB |
testcase_02 | AC | 2,750 ms
186,172 KB |
testcase_03 | TLE | - |
testcase_04 | TLE | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
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 | -- | - |
ソースコード
#yukicoder276D ''' 3ヶ月ぶりの挑戦。 めちゃくちゃフローに見える。計算量が大丈夫な保証まったくないけどやってみるか。 →最小費用流の計算量はO(FE logV) らしい。F=2なら大丈夫だろ。 ''' f=lambda:map(int,input().split()) N,M=f() #最小費用流 Vを入力してください V=N #入力してください G=[[] for i in range(V)]; INF=10**64 # V: 頂点数 def add_edge(u, v, cap, cost): # 最小費用流を見据えて、辺にコストの情報を保持 G[u].append((v,cap, cost,len(G[v]) )) # 順辺: (移動先,容量,費用,逆辺番号)のtuple型 G[v].append((u, 0,-cost,len(G[u])-1)) # 逆辺: コストを負値にする # def bellman_ford(s): # dist=[INF]*V; dist[s]=0 # 全辺をdist=INFで初期化する Pv,Pe=[0]*V,[0]*V # 始点からの具体的な最短距離を求めるため用意 while True: # Pv[v]: 距離更新時に通った頂点 update=False # Pe[v]: Pv[v]の何番目の辺を用いたか for v in range(V): # if dist[v]==INF: continue # 頂点vに考慮が及んでいない時はskipする for i in range(len(G[v])): # G[v]: 遷移先, 容量, 費用, (逆辺の番号) nxt,cap,cost,_=G[v][i] # G[v][i]: 頂点vのi番目の辺 if cap>0 and dist[nxt]>dist[v]+cost: dist[nxt]=dist[v]+cost # 容量0の辺は無視する点に注意 update=True # 距離更新ができた時は次回もループを回す Pv[nxt],Pe[nxt]=v,i # 更に、距離更新用の頂点・辺情報を記録する if not update: break # return dist,Pv,Pe # 距離。最短路用の頂点・辺情報を返す # def Calc_mincost(st,fin,fL): # fL: 流したい水総量 result=0 # while fL>0: # dist,Pv,Pe=bellman_ford(st) # ベルマンフォード法で現時点の最短路を決定 if dist[fin]==INF: return INF # 条件を満たせない場合はINFを返す flow=fL; v=fin # while v!=st: # ①最短路に流せる水量上限を測定 flow=min(flow,G[Pv[v]][Pe[v]][1])# 終点から最短路を逆走しながら水量上限を測定 v=Pv[v] # vをひとつ前の頂点に戻す 始点に戻るまで反復 result+=flow*dist[fin] # 始点に戻った時点で、最終的なフローと距離から fL-=flow; v=fin # コストを計上する。さらにフローの計上処理へ while v!=st: # ②使用した最大水量で通過した辺を更新 u,cap,cost,rev=G[Pv[v]][Pe[v]] # 順辺更新: revの情報は保持しておく cap-=flow # list型よりtuple型のほうが高速なのでバラす G[Pv[v]][Pe[v]]=(u,cap,cost,rev) # 容量だけ更新してtupleで戻す u,cap,cost,rev2=G[v][rev] # 逆辺更新: revの情報をそのまま使う cap+=flow # rev2は順辺番号にあたる G[v][rev] =(u,cap,cost,rev2)# v=Pv[v] # 順辺逆辺を更新したらひとつ前に戻る return result # 総費用をreturn お疲れ様でした for _ in range(M): u,v,c,d=f() add_edge(u-1,v-1,1,c); add_edge(u-1,v-1,1,d) add_edge(v-1,u-1,1,c); add_edge(v-1,u-1,1,d) print(Calc_mincost(0,N-1,2))