택배 배송
골드 IV의견: 0
\(N\)개의 마을이 있고, 마을들은 양방향 도로로 연결되어 있다. 각 도로는 서로 다른 두 마을 \(A\), \(B\)를 잇고, 이 도로를 지나는 데 드는 비용은 \(C\)이다.
택배 기사는 \(1\)번 마을에서 출발하여 \(N\)번 마을까지 택배를 배송하려고 한다. 모든 마을은 도로로 연결되어 있으므로 \(1\)번 마을에서 \(N\)번 마을까지는 항상 갈 수 있다.
\(1\)번 마을에서 \(N\)번 마을까지 가는 데 드는 비용의 최솟값을 구하시오. 두 마을 사이에 여러 개의 도로가 있을 수도 있다.
- \(2 \le N \le 1\,000\)
- \(1 \le M \le 10\,000\)
- \(1 \le A, B \le N\), \(A \ne B\)
- \(1 \le C \le 10\,000\)
- 모든 마을은 도로로 연결되어 있다.
첫째 줄에 마을의 수 \(N\)과 도로의 수 \(M\)이 주어진다. 마을은 \(1\)번부터 \(N\)번까지 번호가 매겨져 있다.
다음 \(M\)개의 줄에 각 도로를 나타내는 세 정수 \(A\), \(B\), \(C\)가 주어진다. 이는 마을 \(A\)와 마을 \(B\)를 잇는, 비용이 \(C\)인 양방향 도로가 있다는 의미이다.
\(1\)번 마을에서 \(N\)번 마을까지 가는 데 드는 비용의 최솟값을 한 줄에 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 40점 | \(2 \le N \le 100\)이고 \(M \le 2\,000\)이다. |
Subtask 2 | 60점 | 추가 제한이 없다. |
5 5
1 2 3
2 3 4
1 3 10
3 4 2
4 5 110\(1 \to 2 \to 3 \to 4 \to 5\) 경로의 비용은 \(3 + 4 + 2 + 1 = 10\)으로 최소이다. (\(1 \to 3\) 도로는 비용이 \(10\)으로 더 비싸다.)
2 1
1 2 77\(1\)번 마을과 \(2\)번 마을을 잇는 유일한 도로의 비용은 \(7\)이다.
rip 작성
출처 지정되지 않음
평가 및 의견
택배 배송
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
택배 배송