[백준/10776] 제국 (Python)

Problem : https://www.acmicpc.net/problem/10776

10776번: 제국

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:06:13

 

---

 

문제 설명

 

 

사회에 불만이 많은 지용이는 미적분학 교과서를 적당히 찢어서, 한 사람이 충분히 탈 만한 두께 K의 뗏목을 만들었다.

지용이는 이제 A 항구에서 출발해서 무인도 B에 자신의 제국을 건설하기 위해 멀고 먼 여행을 떠날 계획이다. (1 ≤ A, B ≤ N, A ≠ B)

바다에는 N개의 섬이 있고 M개의 바닷길이 있으며, 바닷길 외의 길로는 갈 수가 없으며 지용이는 A에서 B로 가는 동안 섬들을 거쳐가면서 항해할 계획이다.

각 바닷길은 지나가는 데 걸리는 시간 ti, 뗏목을 깎아내리는 정도 hi (cm) 를 가지고 있으며, 만약에 도착하기 전에 뗏목이 0cm 이하의 두께를 가지게 된다면 - 달리 말해서 경로 상의 hi의 합이 K 이상이 된다면, 수영을 못하는 지용이의 목숨을 보장하지 못할수도 있다(!)

지용이는 가장 빠른 시간 내에 A에서 B 지점까지 안전하게 가기를 원한다. 지용이를 도와 그러한 길의 길이를 출력해주자.

 

 

입력 및 출력

 

입력

 

첫 번째 줄에는 정수 K, N, M (1 ≤ K ≤ 200; 2 ≤ N ≤ 2000; 1 ≤ M ≤ 10000)이 주어진다.

이 후 M개의 줄에 각 바닷길의 정보가 A, B, ti, hi (1 ≤ A, B ≤ N; 1 ≤ ti ≤ 105; 0 ≤ hi ≤ 200) 형태로 주어진다. 이는 A와 B를 잇는 바닷길이 존재하며, 이 바닷길은 ti의 시간이 걸리며 hi 만큼 뗏목을 깎아내린다는 것을 의미한다. A ≠ B임이 보장된다.

마지막 줄에는 시작점과 도착점인 A, B가 주어진다. (1 ≤ A, B ≤ N; A ≠ B)

 

출력

 

지용이가 안전하게 A에서 B에서 항해할 수 있다면 그 때 걸리는 시간을, 그럴 수 없다면 -1을 출력한다.

 

입력 예시

 

10 4 7
1 2 4 4
1 3 7 2
3 1 8 1
3 2 2 2
4 2 1 6
3 4 1 1
1 4 6 12
1 4

 

출력 예시

 

7

 

 

---

 

풀이

 

2차원 리스트를 통해 다익스트라로 풀이해보자. 저장해야 할 값은 현재 노드와 현재 시점의 남은 뗏목 두께이며, 최소 길이가 되도록 갱신하며 탐색을 진행하면 된다. 우선순위 큐를 사용하므로 도착 시점에 도달하는 순간 최솟값을 취득할 수 있다.

 

 

풀이 코드

from collections import defaultdict
from heapq import *
import sys
input = sys.stdin.readline
MAX = float('inf')

K, N, M = map(int, input().split())
dist = [[MAX]*(K+1) for _ in range(N+1)]
edge_dict = defaultdict(list)

for _ in range(M) :
  a, b, t, h = map(int, input().split())
  edge_dict[a].append((b, t, h))
  edge_dict[b].append((a, t, h))

S, E = map(int, input().split())
dist[S][K] = 0
q = [(0, K, S)]
flg = False
while q :
  d, k, n = heappop(q)
  if n == E :
    flg = True
    break
  for e, t, h in edge_dict[n] :
    if k - h <= 0 :
      continue
    if dist[e][k-h] > d + t :
      dist[e][k-h] = d + t
      heappush(q, (d+t, k-h, e))

print(d if flg else -1)

풀이 완료!