택배 로봇
골드 V의견: 0
배송 회사의 로봇이 도시의 도로망을 이용해 \(S\)번 창고에서 \(T\)번 창고로 이동한다. 도시에는 \(N\)개의 창고와 \(M\)개의 단방향 도로가 있다. 각 도로에는 이동 비용이 정수로 표시되어 있다.
로봇이 \(S\)에서 \(T\)까지 이동하는 데 필요한 최솟값 비용을 구하여라. 경로가 없으면 \(-1\)을 출력하여라.
- \(1 \le N \le 200\,000\)
- \(0 \le M \le 400\,000\)
- \(1 \le S, T \le N\)
- \(1 \le u, v \le N\), \(\;1 \le w \le 10^9\)
- \(S = T\)이면 비용은 \(0\)이다.
첫째 줄에 창고의 수 \(N\), 도로의 수 \(M\), 출발 창고 \(S\), 도착 창고 \(T\)가 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 도로 정보 \(u\), \(v\), \(w\)가 공백으로 구분되어 주어진다. 창고 \(u\)에서 창고 \(v\)로 비용 \(w\)인 단방향 도로가 있음을 의미한다. 같은 두 창고 사이에 여러 도로가 있을 수 있다.
\(S\)에서 \(T\)까지의 최소 이동 비용을 출력한다. 경로가 없으면 \(-1\)을 출력한다.
4 5 1 4
1 2 4
1 3 1
3 2 2
2 4 5
3 4 8
8
\(1 \to 3 \to 2 \to 4\) 경로의 비용은 \(1+2+5=8\)로 가장 저렴하다. 직행 \(1 \to 2 \to 4\)는 \(4+5=9\), \(1 \to 3 \to 4\)는 \(1+8=9\)이다.
4 2 1 4
1 2 10
3 4 5
-1
노드 \(1\)에서 노드 \(4\)로 가는 경로가 없으므로 \(-1\)을 출력한다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
택배 로봇
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
택배 로봇