백준 11779 python1 11779. 최소비용 구하기 2 (Python) 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 출발지가 주어졌고 비용에 음수가 없으므로 다익스트라를 이용하여 출발지에서 도착지까지의 최단 거리를 구할 수 있다. 다익스트라는 링크를 참고하자. 문제에서는 단순히 최단 거리뿐만 아니라 경로까지 요구하고 있다. 이를 위해 prev라는 리스트를 추가하였다. prev[x]는 출발지에서 x까지 최단 거리로 이동할 때 x 지점에 도착하기 이전에 방문했던 지점에 대한 정보를 담고 있다. 예를 들어 start -> a -> b -> x와 .. 2022. 5. 30. 이전 1 다음
