結果
問題 |
No.1283 Extra Fee
|
ユーザー |
![]() |
提出日時 | 2020-11-06 22:31:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,877 ms / 2,000 ms |
コード長 | 3,748 bytes |
コンパイル時間 | 480 ms |
コンパイル使用メモリ | 81,824 KB |
実行使用メモリ | 245,036 KB |
最終ジャッジ日時 | 2024-11-16 06:46:23 |
合計ジャッジ時間 | 26,208 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
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)