結果

問題 No.1301 Strange Graph Shortest Path
ユーザー titiatitia
提出日時 2020-11-28 16:13:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,462 ms / 3,000 ms
コード長 1,670 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 82,076 KB
実行使用メモリ 239,104 KB
最終ジャッジ日時 2024-09-12 23:07:21
合計ジャッジ時間 42,378 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
53,424 KB
testcase_01 AC 41 ms
53,672 KB
testcase_02 AC 1,204 ms
216,052 KB
testcase_03 AC 1,087 ms
194,644 KB
testcase_04 AC 1,419 ms
237,732 KB
testcase_05 AC 1,059 ms
209,584 KB
testcase_06 AC 1,241 ms
216,744 KB
testcase_07 AC 1,226 ms
210,396 KB
testcase_08 AC 1,037 ms
194,084 KB
testcase_09 AC 1,222 ms
211,652 KB
testcase_10 AC 1,055 ms
196,908 KB
testcase_11 AC 1,372 ms
218,796 KB
testcase_12 AC 1,393 ms
221,272 KB
testcase_13 AC 1,341 ms
219,340 KB
testcase_14 AC 1,227 ms
208,560 KB
testcase_15 AC 1,229 ms
207,560 KB
testcase_16 AC 1,454 ms
239,104 KB
testcase_17 AC 1,267 ms
223,368 KB
testcase_18 AC 1,178 ms
205,284 KB
testcase_19 AC 1,307 ms
219,804 KB
testcase_20 AC 1,304 ms
220,992 KB
testcase_21 AC 1,243 ms
221,188 KB
testcase_22 AC 1,330 ms
224,712 KB
testcase_23 AC 1,259 ms
220,356 KB
testcase_24 AC 1,326 ms
220,448 KB
testcase_25 AC 1,462 ms
235,488 KB
testcase_26 AC 1,273 ms
213,800 KB
testcase_27 AC 1,326 ms
217,148 KB
testcase_28 AC 1,069 ms
200,820 KB
testcase_29 AC 1,397 ms
239,056 KB
testcase_30 AC 1,386 ms
231,212 KB
testcase_31 AC 1,393 ms
233,092 KB
testcase_32 AC 41 ms
53,384 KB
testcase_33 AC 548 ms
207,500 KB
testcase_34 AC 1,208 ms
232,920 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
import heapq

N,M=map(int,input().split())

EDGE=[[] for i in range(N+1)]
EDGELIST=[]

eind=0
for i in range(M):
    u,v,c,d=map(int,input().split())
    X=[v,c,1,eind]
    EDGE[u].append(X)
    EDGELIST.append(X)
    eind+=1

    X=[u,-c,0,eind]
    EDGE[v].append(X)
    EDGELIST.append(X)
    eind+=1

    X=[u,c,1,eind]
    EDGE[v].append(X)
    EDGELIST.append(X)
    eind+=1

    X=[v,-c,0,eind]
    EDGE[u].append(X)
    EDGELIST.append(X)
    eind+=1


    X=[v,d,1,eind]
    EDGE[u].append(X)
    EDGELIST.append(X)
    eind+=1

    X=[u,-d,0,eind]
    EDGE[v].append(X)
    EDGELIST.append(X)
    eind+=1

    X=[u,d,1,eind]
    EDGE[v].append(X)
    EDGELIST.append(X)
    eind+=1

    X=[v,-d,0,eind]
    EDGE[u].append(X)
    EDGELIST.append(X)
    eind+=1


start=1
goal=N

BACK=[[-1,-1] for i in range(N+1)]
P=[0]*(N+1)
LA=0

for fl in range(2):
    ANS=[float("inf")]*(N+1)
    Q=[start]
    ANS[start]=0

    while Q:
        x = heapq.heappop(Q)
        time = x>>20
        fr = x - (time<<20)
        if time > ANS[fr]:
            continue

        for to,cost,vol,ind in EDGE[fr]:
            
            if vol>0 and ANS[to]>ANS[fr]+cost:
                
                ANS[to]=ANS[fr]+cost
                BACK[to]=[fr,ind]
                heapq.heappush(Q,((ANS[to])<<20)+to)

    LA+=ANS[goal]+P[goal]

    P=[P[i]+ANS[i] for i in range(N+1)]
 
    NOW=goal
    while NOW!=start:
        fr,ind=BACK[NOW]
        EDGELIST[ind][2]-=1
        EDGELIST[ind^1][2]+=1

        NOW=fr

    for i in range(N+1):
        for j in range(len(EDGE[i])):
            EDGE[i][j][1]+=P[i]-P[EDGE[i][j][0]]

print(LA)
0