Funcia
Lv.3bellman-forddpgraphshortest-path

환승 K번 이하 최저가 항공권

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

0번부터 n - 1번까지 n개의 공항이 있습니다. flights[i] = [a, b, price]는 a번 공항에서 b번 공항으로 가는 직항편이 price원이라는 뜻입니다(반대 방향은 별개입니다).

src번 공항에서 dst번 공항까지 가려고 합니다. 중간에 들르는 공항(환승)은 최대 k번까지만 허용됩니다. 즉 비행기를 최대 k + 1번 탈 수 있습니다. 가능한 가장 싼 총 요금을 반환하고, 갈 수 없으면 -1을 반환하세요.

입출력 예

nflightssrcdstkresult
4[[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 2, 650], [1, 3, 600]]031700
4[[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 2, 650], [1, 3, 600]]032300
3[[0, 1, 5], [1, 2, 5]]020-1

입출력 예 설명

예 1 — 환승 1번 이하로 가는 길은 0 → 1 → 3(100 + 600 = 700)과 0 → 2 → 3(650 + 100 = 750)이므로 700원입니다.

예 2 — 환승을 2번까지 할 수 있으면 0 → 1 → 2 → 3으로 300원에 갈 수 있습니다.

예 3 — 직항편이 없고, 환승은 한 번도 할 수 없습니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(n: int, flights: int[][], src: int, dst: int, k: int) → int

제한 사항

  • 2≤2 \le n ≤1,000\le 1{,}000
  • 0≤M=0 \le M = flights.length ≤6,000\le 6{,}000, 0≤0 \le a, b <n< n, a ≠\ne b, 1≤1 \le price ≤106\le 10^6
  • 같은 두 공항 사이에 직항편이 여러 개 있을 수 있습니다.
  • 0≤0 \le src, dst <n< n, src ≠\ne dst
  • 0≤0 \le k <n< n

기대 복잡도

시간
O(K * (N + M))
공간
O(N + M)

입출력 예

nflightssrcdstk기대 출력
4[[0,1,100],[1,2,100],[2,3,100],[0,2,650],[1,3,600]]031700
4[[0,1,100],[1,2,100],[2,3,100],[0,2,650],[1,3,600]]032300
3[[0,1,5],[1,2,5]]020-1

힌트

힌트

"가장 싼 길"만 찾는 다익스트라는 비행 횟수 제한을 지키지 못합니다. 싸지만 많이 갈아타는 길이 먼저 확정될 수 있기 때문입니다.

비행 횟수를 한 번씩 늘려 가는 벨만-포드를 쓰세요. cost[v]를 "지금까지 허용한 횟수 이내로 v에 도착하는 최소 요금"이라 하고, 라운드마다 모든 항공편 (a, b, p)에 대해 next[b] = min(next[b], cost[a] + p)를 계산합니다.

이때 이전 라운드의 값(cost)으로만 갱신해야 합니다. 같은 라운드에서 방금 바뀐 값을 다시 쓰면 한 라운드에 비행기를 여러 번 탄 셈이 됩니다. k + 1라운드 뒤의 cost[dst]가 답입니다.

복잡도 목표

공항 쌍마다 요금표를 만들어 라운드마다 n2n^2칸을 모두 훑는 O(k⋅n2)O(k \cdot n^2) 풀이는 효율성 테스트에서 시간 초과가 납니다. 라운드마다 항공편 목록만 보는 O(k⋅(n+M))O(k \cdot (n + M))이면 충분합니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4011판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.