[백준 11719번] 파이썬 - 최소 비용 구하기 2

http://www.acmicpc.net/problem/11719

11719번: 그대로 출력하기 2

 

# 조건

• n(1<=n<=1000)의 도시
• 한 도시에서 출발하여 다른 도시에 도착하는 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째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.

 

# 접근 방법 및 Solution

• 전형적인 다익스트라 문제인 것 같다.
• heapq를 이용하여 비용이 적은 것 우선으로 탐색을 해주고
  • (비용, 출발점, 경로기록 리스트) 인자로 사용
• pop을 하였을 때, 도착지라면, 그 때의 비용을 기록해준다.

 

메모리 초과

• 모든 정보 담아주니 메모리 초과

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from heapq import heappop, heappush  
  
  
  
def route(start, end):  
    global result  
    # 비용, 출발점 경로 넣기  
    q =[(0, start, [start])]  
  
    while q:  
        cost, bus_stop, path = heappop(q)  
  
        # 도착지라면 종료  
        if bus_stop == end:  
            if cost < result[0]:  
                result = [cost, path]  
        else:  
            for now_cost, now_stop in way[bus_stop]:  
                if cost + now_cost >= result[0]:  
                    continue  
                else:  
                    heappush(q, (now_cost+cost, now_stop, path +[now_stop]))  
  
  
n = int(input())  
m = int(input())  
way = [[] for _ in range(n+1)]  
  
for _ in range(m):  
    a, b, c, = map(int, input().split())  
    # 비용 먼저 넣어주기  
    heappush(way[a], (c,b))  
  
start, end = map(int, input().split())  
# 결과값 크게 잡아주기  
result = [float('inf'), []]  
  
route(start, end)  
print(result[0])  
print(len(result[1]))  
print(*result[1])

 

pass 코드

• 따라서, 가지치기를 조금 더 해주어야 한다.
• result가 아닌 각 도시까지의 최단 거리를 따로 담아주면 된다.
  • 이미 최소비용을 넘어섰다면 continue해주면 된다.
  • 도착했다면 다익스트라 특성 상 최소 비용이므로 출력 후 종료
• 아래 코드로 예시를 돌리면 예제 출력 1 3 5가 아닌 1 4 5가 나오는데 둘 다 비용이 같으므로 문제 x

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from heapq import heappop, heappush  
  
  
def route(start, end):  
    global result  
    # 결과값 크게 잡아주기  
    dist = [float('inf')] * (n + 1)  
    # 비용, 출발점 경로 넣기  
    q = [(0, start, [start])]  
  
    while q:  
        cost, bus_stop, path = heappop(q)  
        # 도착지라면 종료  
        if bus_stop == end:  
            print(dist[end])  
            print(len(path))  
            print(*path)  
            break  
        for next_cost, next_stop in way[bus_stop]:  
            if cost + next_cost >= dist[next_stop]:  
                continue  
            dist[next_stop] = cost + next_cost  
            heappush(q, (next_cost + cost, next_stop, path + [next_stop]))  
  
  
n = int(input())  
m = int(input())  
way = [[] for _ in range(n + 1)]  
  
for _ in range(m):  
    a, b, c, = map(int, input().split())  
    # 비용 먼저 넣어주기  
    heappush(way[a], (c, b))  
  
start, end = map(int, input().split())  
  
route(start, end)