Day 13.
I come up with what I should do to solve this (namely, double dijkstra), but I didn't because i forgot how to use heapq module.
So I learn heapq first, then after finishing it, I solve the problem.
Code (for studying heapq) is below.
#復習 how to use heapq
from heapq import *
a =
heappush(a,[10,11])
heappush(a,[20,5])
answer,_ = heappop(a)
print(answer)
#10
print(_)
#11
#heapq では、1番目の要素を小さいものから取っていく
- Heapqの公式ドキュメントはこちら。
- ヒープとは、全ての親ノードの値が、そのすべての子の値以下であるような二分木
- 二分木という仮定なので、存在しない葉、節は、無限大としている。
- 親が子以下、ということは、大ボス（大先祖）が一番小さい
- つまり、根が、常に最小
- 根を見つけたら良い
- 根を取った後、並べる作業
- 要素を足した後、並べる作業
- 年齢の逆数は、このような性質？
- 親より子の方が大きい
- 親の親より、親の方が大きい
- いろいろある。
- heapify
- リストを優先度付きキューに変換
- heappush
- 優先度付きキューに要素入れる
- heappop
- 優先度付きキューから最小値を取り出す
- heapify
- 最小値を考えてきたが、－1を掛けたり、逆数にしたら最大値も扱える。
- 気持ちは以下の通り。
- 何か序列があるものを取り出す、取り入れつつ、序列を維持する
- そんな時に計算量を落としたいなら、Heapqを使おう。
- ヒープとは、全ての親ノードの値が、そのすべての子の値以下であるような二分木
- よくわかったので、次に進もう。
Code (of the solution) is below.
import heapq
N,M = map(int,input().split())
G = [ for _ in range(N)]
for _ in range(M):
a,b,c = map(int,input().split())
INF = 10**9
C = [INF for _ in range(N)]
C[s] = 0
H = [(0,s)]
while len(H)>0:
_,v = heapq.heappop(H)
for d, n in G[v]:
if C[n] > C[v] + d:
C[n] = C[v] + d
heapq.heappush(H,(C[n],n))
return C
for i in range(N):
print(First[i]+Last[i])
- 最後に、Dijkstra法について、調べてみる。こちら。
- グラフの2頂点間の最短経路を求めるアルゴリズム
- カーナビの経路探索
- 鉄道の経路案内
- 最短経路の推定値が既知なら、A*アルゴリズムを使って楽にできるらしい。
- さらに、2分木ヒープをしたが、これをフィボナッチヒープにすると、さらに計算量が落ちるらしい
- 物理的に考える試みがあった。
- 操作
- グラフをビー玉と紐で作り、床に置く
- 開始点となるビー玉をつまみ上げた時に、他のビー玉は自由落下が始まる。
- しかし、紐があるので、開始点に近いビー玉から落下が止まる。
- 気持ち
- 最短経路が求めたい
- ビー玉が止まったら、直前のビー玉が何かがわかる。
- どの紐の影響かが解れば良い
- それはつまり、紐のもう片方の端にある、ビー玉を特定すること。
- それを最後から辿っていくと、最初まで戻り（確定し）、無事に最短経路が求まる。
- アルゴリズム的なこと。
- 停止したビー玉の集合、H
- 探索をしない
- 停止したビー玉の隣にあるビー玉の集合（のうち落下しているもの）、A
- キューのこと
- 次に止まるビー玉（最も距離の短いAの要素）を決め、それをHに入れ、それに隣接するものの一部をAに入れる。
- 停止したビー玉の集合、H
- Dijkstraは基本的なアルゴリズムだが、奥が深い。
- 操作
- グラフの2頂点間の最短経路を求めるアルゴリズム
バイバイ！