質問編集履歴
1
変更
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -11,16 +11,11 @@
|
|
|
11
11
|
dist = [float('inf') for _ in range(N)]
|
|
12
12
|
dist[0] = 0
|
|
13
13
|
|
|
14
|
-
seen = [False for _ in range(N)]
|
|
15
|
-
|
|
16
14
|
data = [[0, 0]] #未確定ノード[距離, ノード番号]
|
|
17
15
|
while data:
|
|
18
16
|
pos = heapq.heappop(data)[1]
|
|
19
17
|
|
|
20
|
-
if seen[pos]:
|
|
21
|
-
continue
|
|
22
18
|
|
|
23
|
-
seen[pos] = True
|
|
24
19
|
for node, cost in graph[pos]:
|
|
25
20
|
if dist[pos] + cost < dist[node]:
|
|
26
21
|
dist[node] = dist[pos] + cost
|
|
@@ -45,4 +40,4 @@
|
|
|
45
40
|
```
|
|
46
41
|
|
|
47
42
|
### 質問
|
|
48
|
-
慣れないながらheapを用いてダイクストラ法を実装してみました。テストケースを見ると一つの時間切れ(2000ms超え）を除けば全て正解でした。同じ頂点を何度もみないようにseen配列でそれを管理することで高速化を図ったのですが、尚問題が解決しません。一体どのような箇所に注目して改善すればよろしいのでしょうか。素人質問にて恐縮ですが、お力添えいただける箇所がございましたら、ご教授のほど何卒よろしくお願い申し上げます。
|
|
43
|
+
慣れないながらheapを用いてダイクストラ法を実装してみました。テストケースを見ると一つの時間切れ(2000ms超え）を除けば全て正解でした。同じ頂点を何度もみないようにseen配列でそれを管理することで高速化を図ったり（しなかったり）したのですが、尚問題が解決しません。一体どのような箇所に注目して改善すればよろしいのでしょうか。素人質問にて恐縮ですが、お力添えいただける箇所がございましたら、ご教授のほど何卒よろしくお願い申し上げます。
|