5
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

posted at

# 初期実装

dijkstrasimple.py
``````def divceil(n, k): return 1+(n-1)//k  # n/kの切り上げを返す
def main():
n, m, x, y = map(int, input().split())

graph = [[] for _ in range(n)]

for i in range(m):
s, t, tm, km = map(int, input().split())
s -= 1
t -= 1
graph[s].append((t, tm, km))
graph[t].append((s, tm, km))

mindist = [-1] * n
hq = []
heappush(hq, (0, x-1))
while hq:
dist, node = heappop(hq)
if mindist[node] != -1:
continue
mindist[node] = dist
for i, t, k in graph[node]:
if mindist[i] != -1:
continue
heappush(hq, (divceil(dist, k)*k+t, i))

print(mindist[y-1])
``````

これは最もシンプルなダイクストラの実装。mindistをhheapqから取り出した順に確定していき、mindistが確定していない頂点をheapqに突っ込んでいる。

# 枝刈り高速化⓵ heapqからゴールを取り出した時点でbreak

dijkstraeda1.py
``````def divceil(n, k): return 1+(n-1)//k  # n/kの切り上げを返す

def main():
n, m, x, y = map(int, input().split())

graph = [[] for _ in range(n)]

for i in range(m):
s, t, tm, km = map(int, input().split())
s -= 1
t -= 1
graph[s].append((t, tm, km))
graph[t].append((s, tm, km))

mindist = [-1] * n
hq = []
heappush(hq, (0, x-1))
while hq:
dist, node = heappop(hq)
if node==y-1:
print(dist)
return
if mindist[node] != -1:
continue
mindist[node] = dist
for i, t, k in graph[node]:
if mindist[i] != -1:
continue
heappush(hq, (divceil(dist, k)*k+t, i))

print(-1)
``````

# 枝刈り高速化②heapqに入れる値を制限

dijkstraeda2.py
``````def divceil(n, k): return 1+(n-1)//k  # n/kの切り上げを返す

def main():
n, m, x, y = map(int, input().split())

graph = [[] for _ in range(n)]

for i in range(m):
s, t, tm, km = map(int, input().split())
s -= 1
t -= 1
graph[s].append((t, tm, km))
graph[t].append((s, tm, km))

mindist = [10**20] * n
fixed=[False]*n
hq = []
heappush(hq, (0, x-1))
while hq:
dist, node = heappop(hq)
if node==y-1:
print(dist)
return
if fixed[node]:
continue
fixed[node] = True
for i, t, k in graph[node]:
if divceil(dist, k)*k+t >= mindist[i]:
continue
heappush(hq, (divceil(dist, k)*k+t, i))
mindist[i]=divceil(dist, k)*k+t

print(-1)
``````

このスライドの14~15ページ目と同じ。mindistを、heapqから取り出して確定した距離ではなく、heapqに入れた暫定の最短距離とする。heapqに入れる時に、暫定の最短距離を確認して、それより長い場合heapqに入れないことで、heapqに入れる値の数を減らして、枝刈りすることができる。ただし、距離が確定したかどうかの配列を別に作るので、元から速い場合さらなる高速化にはならないこともある。

### 別実装

https://atcoder.jp/contests/abc192/submissions/22259820

# 枝刈り高速化③heapqにタプルではなく数値を入れる

dijkstraeda3.py
``````def divceil(n, k): return 1+(n-1)//k  # n/kの切り上げを返す

def main():
n, m, x, y = map(int, input().split())

graph = [[] for _ in range(n)]

for i in range(m):
s, t, tm, km = map(int, input().split())
s -= 1
t -= 1
graph[s].append((t, tm, km))
graph[t].append((s, tm, km))

mindist = [10**20] * n
fixed=[False]*n
hq = []
op=lambda d,i:d*n+i
heappush(hq, op(0, x-1))
while hq:
dist, node = divmod(heappop(hq),n)
if node==y-1:
print(dist)
return
if fixed[node]:
continue
fixed[node] = True
for i, t, k in graph[node]:
if divceil(dist, k)*k+t >= mindist[i]:
continue
heappush(hq, op(divceil(dist, k)*k+t, i))
mindist[i]=divceil(dist, k)*k+t

print(-1)
``````

heapqに入れる時、タプルではなく数値の方が高速に動作する。そこで、2つの数値を商と余りとして1つの数値にまとめて保持しておくことで、高速化が見込める。ただしこれも、タプルから数値の計算と数値からタプルの復元が必要なので、元から速い場合さらなる高速化にはならないこともある。

### タプル⇔数値相互変換ライブラリ

2値のタプルと数値の変換ならまだ書きやすいが、3値以上のタプルと数値の変換を直接書くと、コードが汚くなってしまうので、クラスとして処理できる自作ライブラリを紹介する。コンストラクタで、変換したい値のそれぞれの最大値のリストを渡すと、packingでタプルを数値に、unpackingで変換した数値をタプルに戻すことが出来る。使用例は下記ZONeコンE実践例を参照。

tuplepacking.py
``````class tuplepacking:
def __init__(self,maxsizelist):
self.n=len(maxsizelist)
self.maxsizelist=tuple(maxsizelist)

def packing(self,*tuples):
ans=0
for size,tu in zip(self.maxsizelist,tuples):
ans*=size
ans+=tu
return ans

def unpacking(self,value):
ans=[0]*self.n
for i in range(self.n)[::-1]:
value,ans[i]=divmod(value,self.maxsizelist[i])
return ans
``````

# ZONeコンEを上記枝刈り高速化を用いて愚直ダイクストラで通す

こちらの問題では、下方向の複数通りの遷移を、頂点拡張でうまく1つにまとめることで計算方法を削除することが想定解だが、下方向の複数通りの遷移を愚直にループ回しても上記のような適切な枝刈り高速化で間に合わせることが出来る。

# まとめ

ダイクストラは色々な実装があり、その違いで実行時間が大きく変わることもあるので奥が深い

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
What you can do with signing up
5
Help us understand the problem. What are the problem?