드론 배달망
골드 V의견: 0
미래 도시 '리세'에는 \(N\)개의 물류 거점이 있고, 거점 사이를 잇는 \(M\)개의 단방향 항공 경로가 있다. 각 경로에는 드론이 이동하는 데 걸리는 비용(시간·연료 합산)이 정해져 있다.
드론 기지 \(S\)에서 출발하여 각 거점까지 도달하는 최솟값을 구하여라. 도달할 수 없는 거점은 \(-1\)로 표시한다.
같은 경로가 여러 번 주어질 수 있고, 자기 자신으로 가는 경로는 없다.
- \(1 \le N \le 200\,000\)
- \(0 \le M \le 300\,000\)
- \(1 \le S \le N\)
- \(1 \le u, v \le N\), \(u \ne v\)
- \(1 \le w \le 10^9\)
첫째 줄에 거점의 수 \(N\), 경로의 수 \(M\), 출발 거점 \(S\)가 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 경로 정보 \(u\ v\ w\)가 주어진다. 거점 \(u\)에서 거점 \(v\)로 비용 \(w\)로 이동할 수 있다.
거점 \(1\)부터 \(N\)까지, 각 거점까지의 최소 비용을 공백으로 구분하여 한 줄로 출력한다. 출발 거점 \(S\)는 \(0\), 도달 불가능한 거점은 \(-1\)로 출력한다.
4 5 1
1 2 3
1 3 7
2 3 2
2 4 5
3 4 1
0 3 5 6
드론 기지 \(1\)번에서 출발합니다. \(1\to2\): 거리 \(3\), \(1\to2\to3\): 거리 \(3+2=5\) (직접 \(7\)보다 짧음), \(1\to2\to3\to4\): 거리 \(5+1=6\). 따라서 출력은 \(0\ 3\ 5\ 6\)입니다.
3 1 1
1 2 10
0 10 -1
노드 \(3\)은 기지 \(1\)에서 도달할 수 없으므로 \(-1\)을 출력합니다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
드론 배달망
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
드론 배달망