AOJ ALDS1_12_B Single Source Shortest Path I
備忘録
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_B&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() # N個の頂点を持つ有向グラフのデータを生成 # 辺が存在しない場合には値をinfinityとする graph = [[INF] * N 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][v2] = c # ダイクストラ法 dist = [INF] * N # 各頂点までの距離を保持する配列 dist[0] = 0 # 開始始点の頂点は距離をゼロとする visited = [0] * N # 各頂点の訪問状態を保持する配列[0: 未訪問, 1: 訪問済み] while True: min_cost, u = INF, INF # 起点となる頂点の探索 for i in range(N): if min_cost > dist[i] and visited[i] != 1: u = i min_cost = dist[i] # 起点となる頂点が存在しない場合には処理を終了 if u == INF: break visited[u] = 1 # 起点を訪問済みにする # 起点から次の頂点までの距離を更新 for v in range(N): if graph[u][v] != INF and visited[v] != 1: if dist[v] > dist[u] + graph[u][v]: dist[v] = dist[u] + graph[u][v] # 回答 for n in range(N): print(n, dist[n]) if __name__ == '__main__': main()
考え方
螺旋本より、最短経路の問題。
与えられる重み付き有向グラフから、
頂点０を起点として、各頂点までの最短経路を求める。
頂点０から各頂点までの最短経路（単一始点最短経路）を求めるために、
螺旋本の解説通り、ダイクストラ法を用いた。
考え方としては、始点から辺でつながる全ての頂点までの距離をメモし、
始点からつながる頂点の中で、最も距離が短い頂点を次の始点とする。
この時、既に訪問済みの頂点を始点としないようにする。
あとは、辺の距離が近い（重みが小さい）順に、
全ての頂点を訪問するまで処理を繰り返す。
ちなみに、AOJではnumpy, scipyを使用することができないが、
使用可能な環境ではかなり簡潔に書くことができる。
