[테스트케이스 추가] 백준 16681: 등산 66%에서 시간초과나는 경우 python, 파이썬

1. 문제

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

16681번: 등산

2. 풀이

고생을 좀 했는데, 핵심은 (1) 체력을 최소한으로 하는 dijkstra를 찾는다. 성취도와 계산하는 것은 최단거리를 찾은 후에 해도 된다. (이걸 생각하기가 어려웠다) (2) 모든 dijkstra를 찾지 말고 넘어가는 코드를 넣어야한다. (3) 올라갈 때 1->k 와 내려갈때 k->n을 다익스트라 하나의 코드로 작성할 수 있다는 것이다. dijk(1) 이랑 dijk(n) 의 list를 받아서 계산하면 된다.

 

3. 구현

import heapq
import math
import sys

# sys.stdin = open("input.txt")

N,M,D,E = map(int, sys.stdin.readline().split())
h_lis = list(map(int, sys.stdin.readline().split()))

# 점선 그래프 완성
gph=[[] for _ in range(N+2)]
while M:
  M-=1
  a,b,c =map(int,sys.stdin.readline().split())
  gph[a].append((b,c))
  gph[b].append((a,c))
# print(gph)

def dijkstra(node):
    dist=[math.inf for i in range(N+2)]
    edges=[]

    dist[node]=0
    heapq.heappush(edges,(0,node))

    cnt=0
    while edges:
        cost,pos = heapq.heappop(edges)
        
        # 다익스트라에서 시간초과 처리하는 방법.
        if dist[pos]<cost:
            continue
        for p,c in gph[pos]:
            if h_lis[p-1]<=h_lis[pos-1]: # 다음이 낮아지는 방향이면 방문하지 않는다.
                continue
            c+=cost 
            if dist[p]>c:
                dist[p]=c
                heapq.heappush(edges,(c,p))
                cnt+=1
                
        # MST에서 edge 수가 넘어가지 않게 처리하는 코드, 다익스트라는 다르다.
        # if cnt==N+1:
        #     break
    return dist

dist = dijkstra(1)
dist_back = dijkstra(N)

answer = []
for i in range(1,N+1):
    if dist[i] != math.inf and dist_back[i] != math.inf:
        answer.append(h_lis[i-1] * E - (dist[i] + dist_back[i]) * D)
print(max(answer) if answer else 'Impossible')

https://chinpa.tistory.com/15

이 분의 코드를 많이 참고했다.

 

4. 추가 테스트케이스

 

66% 에서 시간초과가 나는 경우 

다익스트라 안에 이미 작은 값을 찾은 경우 continue를 넣어보세요. (전체코드 참조_

시간 초과가 나는 테케를 만들고 싶었지만 너무 큰 수라 렉걸리네요. ㅠㅠ

        # 다익스트라에서 시간초과 처리하는 방법.
        # if dist[pos]<cost:
        #     continue

 

6 6 2 8
1 2 7 11 5 1
1 1 9 
2 3 8 
5 1 7 
5 3 8 
4 5 8 
6 5 7

답 28

 

8 23 10 52
1 24 17 31 10 20 15 1
5 2 82 
3 6 58 
7 6 92 
7 4 72 
8 1 90 
2 3 80 
5 1 79 
5 3 81 
4 5 88 
6 5 72 
6 4 85 
3 5 58 
3 7 51 
3 8 65 
2 6 77 
1 2 96 
1 5 68 
7 2 74 
8 4 52 
2 7 75 
8 5 78 
1 4 90 
8 7 80

답; 192

 

8 14 2 6
1 2 7 11 5 9 15 1
4 7 9
2 1 5 
4 1 9 
6 8 8 
3 1 9 
1 6 6 
7 1 6 
6 7 5 
7 5 8 
6 1 5 
2 5 7 
8 2 5 
6 3 5
4 3 6

답 52

 

8 7 2 3
1 2 7 11 5 9 15 1
6 7 9 
7 5 8 
6 1 4 
2 5 1 
8 2 5 
6 3 5 
5 2 2

답 -9