ALDS1_12_B: Single Source Shortest Path I
始点を決めて、そこからの最短経路を求める問題
Single Source Shortest Path IってことはあとでIIが出てくるってことだな
きっとIでは素直に書けばOKってことだろう
素直に書いた(自分なりに
始点から初めて、隣の頂点までの距離がそれまでの最短記録を更新している隣を探索し続ける
from sys import maxsize
def read_adj():
n = int(input())
adj_list = [[] for _ in range(n)]
for i in range(n):
u, _, *rest = [int(x) for x in input().split()]
for i in range(0, len(rest) - 1, 2):
adj_list[u].append((rest[i], rest[i + 1]))
return n, adj_list
def shortest_path(n, adj_list):
dist = [maxsize] * n
def walk(u):
for v, c in adj_list[u]:
if dist[u] + c < dist[v]:
dist[v] = dist[u] + c
walk(v)
dist[0] = 0
walk(0)
return dist
def print_dist(dist):
for u, d in enumerate(dist):
print(u, d)
def main():
n, adj_list = read_adj()
dist = shortest_path(n, adj_list)
print_dist(dist)
if __name__ == '__main__':
main()
木は作っていない(だめか?
でも問題の要件は満たしてるのでAC
テスト#6が00.41s
木を作るとしたらどうすればよいか
最短記録を更新したときに親頂点を覚えておくくらいで木の情報を持ったことになるかな?
たぶんなるな(確かめない