ただのメモ

他の人に見せても良い方のメモ

Competitive Programing Typical 90 Problem day13

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
        • 優先度付きキューから最小値を取り出す
    • 最小値を考えてきたが、-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())
  G[a-1].append*1
  G[b-1].append*2


def Dijkstra(s):
  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

First = Dijkstra(0)
Last = Dijkstra(N-1)
for i in range(N):
  print(First[i]+Last[i])
  • 最後に、Dijkstra法について、調べてみる。こちら
    • グラフの2頂点間の最短経路を求めるアルゴリズム
      • カーナビの経路探索
      • 鉄道の経路案内
      • 最短経路の推定値が既知なら、A*アルゴリズムを使って楽にできるらしい。
    • さらに、2分木ヒープをしたが、これをフィボナッチヒープにすると、さらに計算量が落ちるらしい
    • 物理的に考える試みがあった。
      • 操作
        • グラフをビー玉と紐で作り、床に置く
        • 開始点となるビー玉をつまみ上げた時に、他のビー玉は自由落下が始まる。
        • しかし、紐があるので、開始点に近いビー玉から落下が止まる。
      • 気持ち
        • 最短経路が求めたい
        • ビー玉が止まったら、直前のビー玉が何かがわかる。
          • どの紐の影響かが解れば良い
          • それはつまり、紐のもう片方の端にある、ビー玉を特定すること。
        • それを最後から辿っていくと、最初まで戻り(確定し)、無事に最短経路が求まる。
      • アルゴリズム的なこと。
        • 停止したビー玉の集合、H
          • 探索をしない
        • 停止したビー玉の隣にあるビー玉の集合(のうち落下しているもの)、A
          • キューのこと
        • 次に止まるビー玉(最も距離の短いAの要素)を決め、それをHに入れ、それに隣接するものの一部をAに入れる。
      • Dijkstraは基本的なアルゴリズムだが、奥が深い。
        • 今回のように、どこかを寄っていく、ということを考えるなら、出発点からのDijkstraと、到着点からのDijkstraをすれば良い
        • グラフ上の2点間の最短経路を求めましょうという気持ちなので、全ての辺の重みが既知でないと厳しい。
        • グラフの形に落とし込むことが大事

バイバイ!

 

 

 

 

 

*1:c,b-1

*2:c,a-1