환승 K번 이하 최저가 항공권
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
0번부터 n - 1번까지 n개의 공항이 있습니다. flights[i] = [a, b, price]는 a번 공항에서 b번 공항으로 가는 직항편이 price원이라는 뜻입니다(반대 방향은 별개입니다).
src번 공항에서 dst번 공항까지 가려고 합니다. 중간에 들르는 공항(환승)은 최대 k번까지만 허용됩니다.
즉 비행기를 최대 k + 1번 탈 수 있습니다. 가능한 가장 싼 총 요금을 반환하고, 갈 수 없으면 -1을 반환하세요.
입출력 예
| n | flights | src | dst | k | result |
|---|---|---|---|---|---|
4 | [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 2, 650], [1, 3, 600]] | 0 | 3 | 1 | 700 |
4 | [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 2, 650], [1, 3, 600]] | 0 | 3 | 2 | 300 |
3 | [[0, 1, 5], [1, 2, 5]] | 0 | 2 | 0 | -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
제한 사항
-
n -
flights.length,a,b,ab,price - 같은 두 공항 사이에 직항편이 여러 개 있을 수 있습니다.
-
src,dst,srcdst -
k
기대 복잡도
- 시간
- O(K * (N + M))
- 공간
- O(N + M)
입출력 예
| n | flights | src | dst | k | 기대 출력 |
|---|---|---|---|---|---|
4 | [[0,1,100],[1,2,100],[2,3,100],[0,2,650],[1,3,600]] | 0 | 3 | 1 | 700 |
4 | [[0,1,100],[1,2,100],[2,3,100],[0,2,650],[1,3,600]] | 0 | 3 | 2 | 300 |
3 | [[0,1,5],[1,2,5]] | 0 | 2 | 0 | -1 |
힌트
힌트
"가장 싼 길"만 찾는 다익스트라는 비행 횟수 제한을 지키지 못합니다. 싸지만 많이 갈아타는 길이 먼저 확정될 수 있기 때문입니다.
비행 횟수를 한 번씩 늘려 가는 벨만-포드를 쓰세요. cost[v]를 "지금까지 허용한 횟수 이내로 v에 도착하는 최소 요금"이라 하고,
라운드마다 모든 항공편 (a, b, p)에 대해 next[b] = min(next[b], cost[a] + p)를 계산합니다.
이때 이전 라운드의 값(cost)으로만 갱신해야 합니다. 같은 라운드에서 방금 바뀐 값을 다시 쓰면 한 라운드에 비행기를 여러 번 탄 셈이 됩니다.
k + 1라운드 뒤의 cost[dst]가 답입니다.
복잡도 목표
공항 쌍마다 요금표를 만들어 라운드마다 칸을 모두 훑는 풀이는 효율성 테스트에서 시간 초과가 납니다. 라운드마다 항공편 목록만 보는 이면 충분합니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1000 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 4 | 판정만 |