Funcia
Lv.3dijkstragraphheapshortest-path

물류 센터에서 가장 빠른 배송

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

0번부터 n - 1번까지 n개의 마을이 있고, 물류 센터는 start번 마을에 있습니다. roads[i] = [a, b, t]는 a번과 b번 마을을 잇는 양방향 도로이며 지나는 데 t분이 걸린다는 뜻입니다.

물류 센터에서 각 마을까지 가는 가장 짧은 시간을 구해, i번째 원소가 i번 마을까지의 시간인 배열을 반환하세요. 도달할 수 없는 마을은 -1, 물류 센터 자신은 0입니다.

입출력 예

nroadsstartresult
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[]

제한 사항

  • 1≤1 \le n ≤100,000\le 100{,}000, 0≤0 \le start <n< n
  • 0≤0 \le roads.length ≤200,000\le 200{,}000
  • roads[i] = [a, b, t], 0≤a,b<n0 \le a, b < n, 1≤t≤1061 \le t \le 10^6
  • 같은 두 마을을 잇는 도로가 여러 개 있거나, 자기 자신으로 가는 도로가 있을 수 있습니다.
  • 시간의 합이 32비트 정수를 넘을 수 있습니다.

기대 복잡도

시간
O((N + M) log N)
공간
O(N + M)

입출력 예

nroadsstart기대 출력
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. 인접 리스트를 만듭니다. 양방향이니 a → b, b → a를 모두 넣습니다.
  2. dist[start] = 0, 나머지는 무한대. 최소 힙에 (0, start)를 넣습니다.
  3. 힙에서 거리가 가장 작은 (d, u)를 꺼냅니다. d > dist[u]면 이미 더 짧은 길로 처리된 오래된 항목이니 건너뜁니다.
  4. u의 이웃 v에 대해 d + t < dist[v]면 갱신하고 힙에 넣습니다.

거리는 최대 105×106=101110^5 \times 10^6 = 10^{11}까지 커질 수 있으니 64비트 정수를 쓰세요.

복잡도 목표

매번 "아직 확정되지 않은 마을 중 가장 가까운 곳"을 배열 전체에서 찾는 방식은 O(N2)O(N^2)라 효율성 테스트에서 시간 초과가 납니다. 힙을 써서 O((N+M)log⁡N)O((N + M) \log N)으로 줄이세요.

언어별 시간 제한

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

테스트 그룹

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

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