GRL_1_A
#aoj_problems
#AOJ解答メモ
#単一始点最短経路問題
#過去問精選100問
問題
単一始点最短経路
https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_A
考察
基本問題
シミュレーション
処理の流れ
実装
ベルマンフォード法
による実装
https://github.com/komo-fr/AOJ/blob/master/answer/GRL_1_A/bellman-ford.py
計算量は
$ O(VE)
ダイクストラ法
による実装(
ヒープ
あり)
heapq
を使う
計算量は
$ O(E logV)
AOJ/dijkstra_with_heapq.py at master · komo-fr/AOJ
ダイクストラ法
による実装(ヒープなし)
計算量は
$ O(V^2)
AOJ上では
TLE
になる
AOJ/dijkstra_without_heapq_TLE.py at master · komo-fr/AOJ
実装上の注意
AtCoder
で同様の問題を解く場合は
scipy.sparse.csgraph.shortest_path
が使える
所感
参考
蟻本
のp95-97