結果
問題 | No.1283 Extra Fee |
ユーザー | uni_python |
提出日時 | 2020-11-06 22:44:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,514 ms / 2,000 ms |
コード長 | 1,570 bytes |
コンパイル時間 | 293 ms |
コンパイル使用メモリ | 87,120 KB |
実行使用メモリ | 133,132 KB |
最終ジャッジ日時 | 2023-08-10 06:05:41 |
合計ジャッジ時間 | 22,285 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 87 ms
71,924 KB |
testcase_01 | AC | 90 ms
71,712 KB |
testcase_02 | AC | 89 ms
71,892 KB |
testcase_03 | AC | 89 ms
71,636 KB |
testcase_04 | AC | 88 ms
71,900 KB |
testcase_05 | AC | 88 ms
71,488 KB |
testcase_06 | AC | 92 ms
71,924 KB |
testcase_07 | AC | 89 ms
71,772 KB |
testcase_08 | AC | 93 ms
72,528 KB |
testcase_09 | AC | 90 ms
71,600 KB |
testcase_10 | AC | 90 ms
71,812 KB |
testcase_11 | AC | 263 ms
81,716 KB |
testcase_12 | AC | 249 ms
82,024 KB |
testcase_13 | AC | 218 ms
80,956 KB |
testcase_14 | AC | 354 ms
86,080 KB |
testcase_15 | AC | 486 ms
89,856 KB |
testcase_16 | AC | 229 ms
80,820 KB |
testcase_17 | AC | 921 ms
127,372 KB |
testcase_18 | AC | 1,356 ms
129,644 KB |
testcase_19 | AC | 1,413 ms
131,876 KB |
testcase_20 | AC | 1,314 ms
128,900 KB |
testcase_21 | AC | 1,360 ms
129,308 KB |
testcase_22 | AC | 1,222 ms
120,572 KB |
testcase_23 | AC | 1,271 ms
124,600 KB |
testcase_24 | AC | 1,338 ms
129,228 KB |
testcase_25 | AC | 1,487 ms
132,880 KB |
testcase_26 | AC | 1,514 ms
132,456 KB |
testcase_27 | AC | 1,470 ms
132,888 KB |
testcase_28 | AC | 1,471 ms
133,132 KB |
testcase_29 | AC | 946 ms
132,300 KB |
ソースコード
import sys input=sys.stdin.readline def I(): return int(input()) def MI(): return map(int, input().split()) def LI(): return list(map(int, input().split())) """ i番目の関所で権利を使うとして, そこまでのコスト+そこからのコスト 関所を通らない時もあるので,素の最短距離も出しておく """ N,M=MI() from collections import defaultdict dd = defaultdict(int) C=[] for _ in range(M): h,w,c=MI() h-=1 w-=1 v=h*N+w C.append((v,c)) dd[v]=c C.sort() def dec(v): i,j=divmod(v,N) return i,j dx=[0,0,1,-1] dy=[1,-1,0,0] ### import heapq inf=float("inf") def calc(st): used=[0]*(N**2) d=[inf]*(N**2) d[st]=0 S=0#usedの和 hq=[(0,st)]#見た頂点の(最短経路長さ,番号) while hq: t,v=heapq.heappop(hq) if used[v]: continue used[v]=1 S+=1 i,j=dec(v) for k in range(4): ni=i+dx[k] nj=j+dy[k] if 0<=ni<N and 0<=nj<N: nv=ni*N+nj if used[nv]: continue cost=dd[nv]+1 dtemp=d[v]+cost if d[nv]<=dtemp: continue d[nv]=dtemp heapq.heappush(hq,(dtemp,nv)) return d ### dgo=calc(0) dba=calc(N*N -1) ans=dgo[-1] # print(ans) for v,c in C: temp=dgo[v]+dba[v]-c*2 # print(v,c,temp) ans=min(ans,temp) print(ans)