結果

問題 No.1301 Strange Graph Shortest Path
ユーザー navel_tosnavel_tos
提出日時 2023-05-16 23:42:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,032 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,680 KB
実行使用メモリ 199,424 KB
最終ジャッジ日時 2024-05-08 16:07:17
合計ジャッジ時間 11,837 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
60,752 KB
testcase_01 AC 38 ms
54,132 KB
testcase_02 AC 2,774 ms
184,888 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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder276D

'''
3ヶ月ぶりの挑戦。

めちゃくちゃフローに見える。計算量が大丈夫な保証まったくないけどやってみるか。
→最小費用流の計算量はO(FE logV) らしい。F=2なら大丈夫だろ。
'''
import sys; input=sys.stdin.readline
f=lambda:map(int,input().split())
N,M=f()

#最小費用流 Vを入力してください
V=N #入力してください

G=[[] for i in range(V)]; INF=10**19         # 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))
0