Lv.3dijkstragraphheapshortest-path
물류 센터에서 가장 빠른 배송
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
0번부터 n - 1번까지 n개의 마을이 있고, 물류 센터는 start번 마을에 있습니다.
roads[i] = [a, b, t]는 a번과 b번 마을을 잇는 양방향 도로이며 지나는 데 t분이 걸린다는 뜻입니다.
물류 센터에서 각 마을까지 가는 가장 짧은 시간을 구해, i번째 원소가 i번 마을까지의 시간인 배열을 반환하세요.
도달할 수 없는 마을은 -1, 물류 센터 자신은 0입니다.
입출력 예
| n | roads | start | result |
|---|---|---|---|
4 | [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 5]] | 0 | [0, 3, 1, 8] |
3 | [[0, 1, 7]] | 1 | [7, 0, -1] |
입출력 예 설명
예 1 — 1번 마을은 직행(4분)보다 0 → 2 → 1(1 + 2 = 3분)이 빠릅니다. 3번 마을은 그 뒤 5분을 더해 8분입니다.
예 2 — 2번 마을로 가는 도로가 없습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(n: int, roads: int[][], start: int) → long[]
제한 사항
-
n,start -
roads.length roads[i] = [a, b, t], ,- 같은 두 마을을 잇는 도로가 여러 개 있거나, 자기 자신으로 가는 도로가 있을 수 있습니다.
- 시간의 합이 32비트 정수를 넘을 수 있습니다.
기대 복잡도
- 시간
- O((N + M) log N)
- 공간
- O(N + M)
입출력 예
| n | roads | start | 기대 출력 |
|---|---|---|---|
4 | [[0,1,4],[0,2,1],[2,1,2],[1,3,5]] | 0 | [0,3,1,8] |
3 | [[0,1,7]] | 1 | [7,0,-1] |
힌트
힌트
가중치가 모두 양수인 그래프의 한 출발점 최단 거리, 다익스트라 알고리즘입니다.
- 인접 리스트를 만듭니다. 양방향이니
a → b,b → a를 모두 넣습니다. dist[start] = 0, 나머지는 무한대. 최소 힙에(0, start)를 넣습니다.- 힙에서 거리가 가장 작은
(d, u)를 꺼냅니다.d > dist[u]면 이미 더 짧은 길로 처리된 오래된 항목이니 건너뜁니다. u의 이웃v에 대해d + t < dist[v]면 갱신하고 힙에 넣습니다.
거리는 최대 까지 커질 수 있으니 64비트 정수를 쓰세요.
복잡도 목표
매번 "아직 확정되지 않은 마을 중 가장 가까운 곳"을 배열 전체에서 찾는 방식은 라 효율성 테스트에서 시간 초과가 납니다. 힙을 써서 으로 줄이세요.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 292 ms | 추정 |
| C++ (GCC, gnu++23) | 292 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1816 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1584 ms | 추정 |
| C# 14 (.NET 10) | 1584 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 2 | 입력·출력 공개 |
| correctness | 40 | 9 | 판정만 |
| performance | 60 | 4 | 판정만 |