kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

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

木を作るとしたらどうすればよいか
最短記録を更新したときに親頂点を覚えておくくらいで木の情報を持ったことになるかな?
たぶんなるな(確かめない