結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー | matsu7874 |
提出日時 | 2015-11-29 19:25:34 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 627 ms / 5,000 ms |
コード長 | 3,365 bytes |
コンパイル時間 | 111 ms |
コンパイル使用メモリ | 11,288 KB |
実行使用メモリ | 14,252 KB |
最終ジャッジ日時 | 2023-10-12 05:46:26 |
合計ジャッジ時間 | 2,799 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 21 ms
8,964 KB |
testcase_01 | AC | 22 ms
8,912 KB |
testcase_02 | AC | 21 ms
8,744 KB |
testcase_03 | AC | 21 ms
8,972 KB |
testcase_04 | AC | 41 ms
9,800 KB |
testcase_05 | AC | 61 ms
10,712 KB |
testcase_06 | AC | 84 ms
11,652 KB |
testcase_07 | AC | 31 ms
9,276 KB |
testcase_08 | AC | 32 ms
9,360 KB |
testcase_09 | AC | 29 ms
9,324 KB |
testcase_10 | AC | 34 ms
9,432 KB |
testcase_11 | AC | 37 ms
9,424 KB |
testcase_12 | AC | 33 ms
9,308 KB |
testcase_13 | AC | 30 ms
9,412 KB |
testcase_14 | AC | 33 ms
9,448 KB |
testcase_15 | AC | 31 ms
9,396 KB |
testcase_16 | AC | 30 ms
9,200 KB |
testcase_17 | AC | 32 ms
9,404 KB |
testcase_18 | AC | 31 ms
9,404 KB |
testcase_19 | AC | 31 ms
9,228 KB |
testcase_20 | AC | 32 ms
9,380 KB |
testcase_21 | AC | 30 ms
9,328 KB |
testcase_22 | AC | 31 ms
9,368 KB |
testcase_23 | AC | 34 ms
9,348 KB |
testcase_24 | AC | 34 ms
9,428 KB |
testcase_25 | AC | 31 ms
9,244 KB |
testcase_26 | AC | 31 ms
9,404 KB |
testcase_27 | AC | 22 ms
8,864 KB |
testcase_28 | AC | 627 ms
14,252 KB |
testcase_29 | AC | 21 ms
8,868 KB |
ソースコード
import heapq import collections class Graph: def __init__(self, size): self.size = size self.graph = [[] for i in range(size)] def add_edge(self, source, target, cost): self.graph[source].append(self.Edge(target, cost)) def add_bidirectional_edge(self, source, target, cost): self.add_edge(source, target, cost) self.add_edge(target, source, cost) def neighbors_of(self, n): res = [] for e in self.graph[n]: res.append(e.target) return res def min_dist_dijkstra(self, s): dist = [float('inf')] * self.size dist[s] = 0 q = [(0, s)] while q: node = self.Node(*heapq.heappop(q)) v = node.id if dist[v] < node.dist: continue for e in self.graph[v]: if dist[e.target] > dist[v] + e.cost: dist[e.target] = dist[v] + e.cost heapq.heappush(q, (dist[e.target], e.target)) return dist def min_path_dijkstra(self, s, t): dist = [float('inf')] * self.size prev = [-1] * self.size dist[s] = 0 q = [(0, s)] while q: node = self.Node(*heapq.heappop(q)) v = node.id if dist[v] < node.dist: continue for e in self.graph[v]: if dist[e.target] > dist[v] + e.cost: dist[e.target] = dist[v] + e.cost heapq.heappush(q, (dist[e.target], e.target)) prev[e.target] = v elif dist[e.target] == dist[v] + e.cost and prev[e.target] > v: heapq.heappush(q, (dist[e.target], e.target)) prev[e.target] = v if v == t: break path = [t] while path[-1] > -1: path.append(prev[path[-1]]) return path[:-1] def min_dist_queue(self, s): dist = [float('inf')] * self.size dist[s] = 0 q = collections.deque() q.append(s) while q: v = q.popleft() for e in self.graph[v]: if dist[e.target] > dist[v] + e.cost: dist[e.target] = dist[v] + e.cost if e.cost == 0: q.appendleft(e.target) else: q.append(e.target) return dist def __str__(self): res = '' for i in range(self.size): res += str(i) for e in self.graph[i]: res += ' ' + str(e.target) res += '\n' return res class Edge: def __init__(self, target, cost): self.target = target self.cost = cost class Node: def __init__(self, dist, i): self.dist = dist self.id = i def __cmp__(self, other): if self.dist < other.dist: return -1 elif self.dist == other.dist: return 0 else: return 1 n, m, start, goal = map(int, input().split()) g = Graph(n) for i in range(m): a, b, c = map(int, input().split()) g.add_bidirectional_edge(a, b, c) print(' '.join(str(x) for x in g.min_path_dijkstra(goal, start))) dist = g.min_dist_dijkstra(goal)