11779 최소비용 구하기 2

hey hey·2022년 1월 18일
0

알고리즘

목록 보기
31/57
post-thumbnail

문제

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

입력

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.

셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다.

풀이

평범한 다익스트라 문제입니다. 조금 다른 점이 있다면 경로를 전부 출력해야 하는 문제 입니다 . heapq를 이용했고 마지막 값으로 리스트에 지나온 길들을 하나씩 추가해서 결과값을 도출합니다.
다음 값이 지나온 경로에 없을 때만 추가를 해주며, 한번이라도 지나온 길은 다시 돌아 순회하지 않게 for문이 나닌 pop으로 모든 값을 없애주면서 처리하면 메모리를 아낄 수 있습니다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from heapq import heappush,heappop

N = int(input())
M = int(input())

graph = [[]for _ in range(N+1)]
for _ in range(M):
    a,b,d = map(int,input().split())
    heappush(graph[a],[d,b])

def bfs(START):
    route = [START] # 다녀온 길을 체크합니다.
    Q = [[0,START,route]]   # [총 경로의 길이, 현재위치, 경로] 순서로 bfs를 순회합니다

    while Q :
        cnt, start, route = heappop(Q)
        if start == END:    # 만일 도착지가 목적지라면
            print(cnt)      # 출력하고 끝냅니다.
            print(len(route))
            print(*route)
            return
        while graph[start]: # 원래라면 for 문으로 전부 순회를 할텐데
            distance,end = heappop(graph[start])    # 순회하지 못하게 그냥 없애버립니다.
            if end not in route:                # 다음 목적지가 route에 없으면
                heappush(Q,[cnt+distance,end,route+[end]])  # Q에 넣고 진행합니다.

START, END = map(int,input().split())
bfs(START)
profile
FE - devp

0개의 댓글