[백준] 11779 최소비용 구하기 2 python

https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

최소 거리를 구하고 경로도 같이 구해야하는데 다익스트라 알고리즘에 경로도 같이 추가하면 쉽게 풀린다.

# import sys; input = sys.stdin.readline
from heapq import heappop, heappush

def dijkstra(s, e, adj_list):
    INF = 987654321
    ret = None # dist, route
    h = [(0, [s], s)]
    visit = [0 for _ in range(len(adj_list))]
    while h:
        dist, route, cur = heappop(h)
        if cur == e:
            ret = (str(dist), str(len(route)), ' '.join(map(str, route)))
            break
        if visit[cur]:
            continue
        visit[cur] = 1
        for adj_dist, adj in adj_list[cur]:
            heappush(h, (adj_dist + dist, route+[adj], adj))

    return ret

def main():
    n, m = int(input()), int(input())
    adj_list = [[] for _ in range(n + 1)]
    for _ in range(m):
        s, e, c = map(int, input().split())
        adj_list[s].append((c, e))
    s, e = map(int, input().split())
    answer = dijkstra(s, e, adj_list)
    print('\n'.join(answer))

if __name__ == "__main__":
    main()