[BOJ/백준] 1162 도로포장 파이썬

문제 링크 : https://www.acmicpc.net/problem/1162

1162번: 도로포장

 

처음 풀이가 맞았는데 오타 때문에 지우고 다시 풀다가 오타를 발견하고 원래코드로 돌아와 푼 바보같은 문제였다.

하지만 결국 시간초과랑 싸운 문제이다.

 

알고리즘은 간단하다.

우선 최단경로를 구해야하므로 다익스트라를 사용했다.

그리고 각 노드를 방문했을 때의 상태가 달라야한다. 상태는 도로를 포장한 개수이다.

다음 도로를 포장하고 갈지 아니면 그냥 갈지 선택해서 다익스트라를 진행하면 된다.

주의할 점은 노드 사이의 가중치가 최대 1백만이고 도로의 수가 최대 5만개 이므로 총 거리가 최대 500억까지 갈수 있음을 유의하자.

 

근데 시간초과가 계속 났다.

큐에서 뺐을 때의 총 거리와 방문체크를 하면서 기록한 총 거리가 다를 때 안하면 되는데 나는 그냥 또 진행하라고 했었다.

그래서 계속 43%였나 거기서 시간초과가 났었다.

 

골드1 문제이지만 벽 부수고 이동하기 이런 문제를 풀어봤다면 알고리즘 떠올리는 것 어렵지 않을 것 같다.

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

2206번: 벽 부수고 이동하기

 

from sys import stdin
from heapq import heappush, heappop

input = stdin.readline
INF = 98765432100

n,m,k = map(int, input().split())

adj_list = [[] for _ in range(n)]
for _ in range(m):
    a,b,c = map(int, input().split())
    adj_list[a-1].append((b-1,c))
    adj_list[b-1].append((a-1,c))

def solv():
    visited = [[INF]*(k+1) for _ in range(n)]
    pq = [(0,0,0)]
    visited[0][0] = 0
    while pq:
        total,cnt,now = heappop(pq)
        if total > visited[now][cnt]:
            continue
        if now == n-1:
            print(total)
            return
        for nxt,cost in adj_list[now]:
            nxt_total = total + cost
            if visited[nxt][cnt] > nxt_total:
                visited[nxt][cnt] = nxt_total
                heappush(pq,(nxt_total,cnt,nxt))

            if cnt+1 <= k and visited[nxt][cnt+1] > total:
                visited[nxt][cnt+1] = total
                heappush(pq, (total, cnt+1, nxt))

solv()