結果
問題 | No.1283 Extra Fee |
ユーザー | iby |
提出日時 | 2020-11-29 00:44:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,049 ms / 2,000 ms |
コード長 | 2,673 bytes |
コンパイル時間 | 139 ms |
コンパイル使用メモリ | 82,052 KB |
実行使用メモリ | 202,564 KB |
最終ジャッジ日時 | 2024-04-27 23:43:56 |
合計ジャッジ時間 | 15,577 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 35 ms
54,076 KB |
testcase_01 | AC | 35 ms
53,524 KB |
testcase_02 | AC | 34 ms
55,216 KB |
testcase_03 | AC | 33 ms
54,112 KB |
testcase_04 | AC | 35 ms
54,036 KB |
testcase_05 | AC | 33 ms
53,896 KB |
testcase_06 | AC | 36 ms
54,824 KB |
testcase_07 | AC | 35 ms
53,212 KB |
testcase_08 | AC | 38 ms
56,320 KB |
testcase_09 | AC | 36 ms
53,928 KB |
testcase_10 | AC | 34 ms
54,244 KB |
testcase_11 | AC | 219 ms
84,708 KB |
testcase_12 | AC | 202 ms
85,128 KB |
testcase_13 | AC | 184 ms
82,536 KB |
testcase_14 | AC | 326 ms
99,296 KB |
testcase_15 | AC | 396 ms
110,504 KB |
testcase_16 | AC | 228 ms
85,184 KB |
testcase_17 | AC | 946 ms
192,612 KB |
testcase_18 | AC | 931 ms
185,456 KB |
testcase_19 | AC | 935 ms
190,268 KB |
testcase_20 | AC | 901 ms
182,512 KB |
testcase_21 | AC | 944 ms
185,060 KB |
testcase_22 | AC | 829 ms
174,000 KB |
testcase_23 | AC | 820 ms
192,008 KB |
testcase_24 | AC | 824 ms
192,112 KB |
testcase_25 | AC | 982 ms
193,400 KB |
testcase_26 | AC | 1,014 ms
193,904 KB |
testcase_27 | AC | 949 ms
193,276 KB |
testcase_28 | AC | 946 ms
193,524 KB |
testcase_29 | AC | 1,049 ms
202,564 KB |
ソースコード
import heapq class Graph(): def __init__(self, N, Type): self._V = N # 頂点の数 self._E = 0 # 辺の数 self.type = Type if Type == "D": # 2次元リスト self.G = [[] for i in range(self._V+1)] elif Type == "W": # 隣接行列 self.G = [[float("inf") for i in range(self._V+1)] for j in range(self._V+1)] elif Type == "B" or Type == "K": # 1次元リスト self.G = [] def E(self): """ 辺数 """ return self._E @property def V(self): """ 頂点数 """ return self._V def add(self, _from, _to, _cost): """ 2頂点と、辺のコストを追加する """ self._E += 1 if self.type == "D": self.G[_from].append((_to, _cost)) elif self.type == "W": self.G[_from][_to] = _cost elif self.type == "B" or self.type == "K": self.G.append((_from, _to, _cost)) def add_both(self, _from, _to, _cost): """ 2頂点と、辺のコストを追加する (無向グラフ) """ self.add(_from, _to, _cost) self.add(_to, _from, _cost) class Dijkstra(Graph): def __init__(self, N): super().__init__(N, "D") self.d = [10**20]*(self._V + 1) self.que = [] heapq.heapify(self.que) def shortest_path(self, s): for i in range(self._V+1): self.d[i] = 10**20 self.d[s] = 0 heapq.heappush(self.que, (0, s)) while self.que: cost, v = heapq.heappop(self.que) if self.d[v] < cost: continue for node, cost in self.G[v]: if self.d[node] > self.d[v] + cost: self.d[node] = self.d[v] + cost heapq.heappush(self.que, (self.d[node], node)) return self.d N, M = map(int, input().split()) dif = [(-1, 0), (1, 0), (0, 1), (0, -1)] cost = [0]*(N**2) G = Dijkstra(N**2) Gs = Dijkstra(N**2) def press(i, j): return N*i + j for i in range(M): h, w, c = map(int, input().split()) h -= 1 w -= 1 cost[press(h, w)] = c inf = 1 << 60 for i in range(N): for j in range(N): now = press(i, j) for dx, dy in dif: if 0 <= dx + i < N and 0 <= dy + j < N: adj = press(dx+i, dy + j) G.add(now, adj, cost[adj] + 1) Gs.add(now,adj, cost[now] + 1) G_s = G.shortest_path(0) Gs_g = Gs.shortest_path(N**2 - 1) ans = inf for i in range(1, N**2 - 1): ans = min(ans, G_s[i] + Gs_g[i] - cost[i]) print(ans)