結果
問題 | No.1283 Extra Fee |
ユーザー | uni_python |
提出日時 | 2020-11-06 22:31:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,538 ms / 2,000 ms |
コード長 | 3,748 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 82,028 KB |
実行使用メモリ | 245,196 KB |
最終ジャッジ日時 | 2024-04-27 23:22:18 |
合計ジャッジ時間 | 21,568 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
54,764 KB |
testcase_01 | AC | 40 ms
56,148 KB |
testcase_02 | AC | 41 ms
55,800 KB |
testcase_03 | AC | 37 ms
54,876 KB |
testcase_04 | AC | 37 ms
55,068 KB |
testcase_05 | AC | 35 ms
55,648 KB |
testcase_06 | AC | 38 ms
57,104 KB |
testcase_07 | AC | 36 ms
55,740 KB |
testcase_08 | AC | 39 ms
56,540 KB |
testcase_09 | AC | 38 ms
55,424 KB |
testcase_10 | AC | 37 ms
56,588 KB |
testcase_11 | AC | 192 ms
84,908 KB |
testcase_12 | AC | 168 ms
86,496 KB |
testcase_13 | AC | 149 ms
82,820 KB |
testcase_14 | AC | 331 ms
104,056 KB |
testcase_15 | AC | 462 ms
120,192 KB |
testcase_16 | AC | 172 ms
85,784 KB |
testcase_17 | AC | 1,146 ms
213,460 KB |
testcase_18 | AC | 1,363 ms
226,808 KB |
testcase_19 | AC | 1,538 ms
239,840 KB |
testcase_20 | AC | 1,386 ms
225,896 KB |
testcase_21 | AC | 1,393 ms
226,980 KB |
testcase_22 | AC | 1,262 ms
212,260 KB |
testcase_23 | AC | 1,425 ms
231,252 KB |
testcase_24 | AC | 1,425 ms
240,412 KB |
testcase_25 | AC | 1,527 ms
244,764 KB |
testcase_26 | AC | 1,515 ms
244,644 KB |
testcase_27 | AC | 1,483 ms
245,076 KB |
testcase_28 | AC | 1,509 ms
245,196 KB |
testcase_29 | AC | 1,180 ms
228,440 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())) ########################################## import heapq class Dijkstra(): """ ・有向 / 無向は問わない(無向の場合は,逆向きの辺もたす) ・負のコストがない場合のみ ・計算量はO(E log|V|) ・heapを使うことで頂点を走査する必要がなくなる(代わりに,距離更新したものは確定でなくともqueに入れておく) ・復元なし """ #最短のpathをたす class Edge(): #重み付き有向辺 def __init__(self, _to, _cost): self.to =_to self.cost = _cost def __init__(self, V): #引数Vは頂点数 self.inf=float('inf') self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺 self. _E = 0 #辺の数 self._V = V #頂点数 #proparty - 辺の数 def E(self): return self._E #proparty - 頂点数 def V(self): return self._V def add(self, _from, _to, _cost): #2頂点と辺のコストを追加 self.G[_from].append(self.Edge(_to,_cost)) self._E +=1 def add2(self, _from, _to, _cost): #2頂点と辺のコスト(無向)を追加 self.G[_from].append(self.Edge(_to, _cost)) self.G[_to].append(self.Edge(_from, _cost)) self._E +=2 def shortest_path(self,s):#,g): #始点sから頂点iまでの最短経路長のリストを返す que = [] #priority queue d = [self.inf] * self.V() #prev = [None]*self.V() #prev[j]は,sからjへ最短経路で行くときのjの一つ前の場所 #復元で使う d[s] = 0 heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加 while len(que)!=0: #キューに格納されてある中で一番コストが小さい頂点を取り出す cost,v = heapq.heappop(que) #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ if d[v] < cost: continue #頂点vに隣接する各頂点iに対して,vを経由した場合の距離を計算して,これがd[i]よりも小さい場合に更新 for i in range(len(self.G[v])): e = self.G[v][i] #vのi個目の隣接辺 if d[e.to] > d[v] + e.cost: d[e.to] = d[v] + e.cost #更新 heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加 return d ######################## """ 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() dx=[0,0,1,-1] dy=[1,-1,0,0] djk=Dijkstra(N**2) ite=0 for i in range(N): for j in range(N): for k in range(4): ni=i+dx[k] nj=j+dy[k] if 0<=ni<N and 0<=nj<N: v=i*N + j nv=ni*N + nj cost=dd[nv]+1 djk.add(v,nv,cost) dgo=djk.shortest_path(0) dba=djk.shortest_path(N**2-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)