結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー | titia |
提出日時 | 2020-11-28 07:19:48 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,448 bytes |
コンパイル時間 | 488 ms |
コンパイル使用メモリ | 82,368 KB |
実行使用メモリ | 232,064 KB |
最終ジャッジ日時 | 2024-09-12 22:05:40 |
合計ジャッジ時間 | 34,471 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 37 ms
53,912 KB |
testcase_01 | AC | 38 ms
53,044 KB |
testcase_02 | WA | - |
testcase_03 | AC | 895 ms
194,144 KB |
testcase_04 | AC | 1,162 ms
230,220 KB |
testcase_05 | AC | 879 ms
209,704 KB |
testcase_06 | AC | 1,020 ms
211,736 KB |
testcase_07 | AC | 1,037 ms
208,536 KB |
testcase_08 | AC | 887 ms
194,776 KB |
testcase_09 | AC | 962 ms
206,192 KB |
testcase_10 | WA | - |
testcase_11 | AC | 1,047 ms
214,188 KB |
testcase_12 | AC | 1,026 ms
215,780 KB |
testcase_13 | AC | 1,079 ms
217,436 KB |
testcase_14 | AC | 1,002 ms
205,340 KB |
testcase_15 | AC | 1,003 ms
204,628 KB |
testcase_16 | AC | 1,157 ms
231,212 KB |
testcase_17 | AC | 1,043 ms
220,016 KB |
testcase_18 | AC | 954 ms
200,684 KB |
testcase_19 | AC | 1,054 ms
213,252 KB |
testcase_20 | AC | 1,006 ms
213,352 KB |
testcase_21 | AC | 995 ms
218,132 KB |
testcase_22 | AC | 1,033 ms
217,084 KB |
testcase_23 | AC | 1,049 ms
218,180 KB |
testcase_24 | AC | 1,032 ms
213,656 KB |
testcase_25 | AC | 1,122 ms
228,028 KB |
testcase_26 | AC | 990 ms
209,748 KB |
testcase_27 | AC | 1,030 ms
213,844 KB |
testcase_28 | AC | 915 ms
202,028 KB |
testcase_29 | WA | - |
testcase_30 | AC | 1,111 ms
225,252 KB |
testcase_31 | AC | 1,079 ms
227,356 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 903 ms
227,124 KB |
ソースコード
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)] LA=0 for fl in range(2): ANS=[float("inf")]*(N+1) Q=[(0,start)] ANS[start]=0 while Q: time,fr = heapq.heappop(Q) 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],to)) LA+=ANS[goal] NOW=goal while NOW!=start: fr,ind=BACK[NOW] EDGELIST[ind][2]-=1 EDGELIST[ind^1][2]+=1 NOW=fr print(LA)