AOJ ALDS1_12_C Single Source Shortest Path II

備忘録

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_C&lang=jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()

    # (距離, 接する頂点)の情報を持つ有向グラフのデータを生成
    graph = [[] for _ in range(N)]
    for _ in range(N):
        v1, k, *vertices = il()
        for idx in range(0, k * 2, 2):
            v2, c = vertices[idx:idx + 2]
            graph[v1].append((c, v2))

    # ダイクストラ法（優先度付きキュー）
    dist = [INF] * N    # 各頂点までの距離を保持する配列
    dist[0] = 0         # 開始始点の頂点は距離をゼロとする
    visited = [0] * N   # 各頂点の訪問状態を保持する配列[0: 未訪問, 1: 訪問済み]
    heap = [(0, 0)]     # 距離と始点頂点（自分自身への移動距離はゼロ）
    heapq.heapify(heap) # 距離と頂点の情報を距離で優先度付きキューとする
    while heap:
        # 頂点uとuに到達するまでの距離
        min_cost, u = heapq.heappop(heap)

        # さらに小さい距離で既に到達済みの場合はcontinue
        if dist[u] < min_cost: continue
        visited[u] = 1  # 頂点uを訪問済みにする

        # グラフの情報から接する頂点と移動距離を順に処理
        for cost, v in graph[u]:
            if visited[v] != 1:
                if dist[u] + cost < dist[v]:
                    # 未到達かつ小さい距離で移動できる場合には
                    # 距離の更新と優先度付きキューに(距離, 頂点)の情報を追加
                    dist[v] = dist[u] + cost
                    heapq.heappush(heap, (dist[v], v))
    # 回答
    for n in range(N):
        print(n, dist[n])


if __name__ == '__main__':
    main()

考え方

螺旋本より、最短経路の発展問題。
ダイクストラ法を用いて、頂点０から各頂点までの最短距離を求める。
ただし、ダイクストラ法の高速化が求められる。

ALDS1_12_B Single Source Shortest Path Iとほぼ同じ問題だが、
制約の頂点数が100倍になっている。
そのため、ALDS1_12_Bと同じ回答を行うと、メモリ制限の超過によりエラーとなる。

メモリ制限内に収めるためには、優先度付きキューを使用して、ダイクストラ法の高速化を行う。
優先度付きキューを使用しない場合には、
始点の頂点から別の全ての頂点のうち最も近い頂点を次の始点とする。
そのため、各頂点において、全ての頂点を探索する必要がある。

優先度付きキューを使用することで、
各頂点からつながる別の頂点の探索のみを行う。
つまり、探索を行なう回数は各頂点 + 辺の数となる。

実装は、データの持ち方を(移動距離, 頂点の値)とし、
各頂点から別の頂点に移動する際、移動距離が最短になる移動のみをキューに追加する。
後はキューを全て探索することで、最短距離を求めることが出来る。