골드 IV
rip
골드 II
★★★★★
2026-06-05 21:49
좋은 문제
R00034
한 번의 무료 이동
레이팅
의견: 1
설명
\(N\)개의 도시와 \(M\)개의 양방향 도로가 있다.
각 도로를 지나갈 때는 정해진 비용이 든다.
당신은 도시 \(1\)에서 도시 \(N\)까지 이동하려고 한다.
단, 이동 중 딱 한 번, 어떤 도로 하나를 비용 \(0\)으로 지나갈 수 있는 무료 이동권을 사용할 수 있다.
무료 이동권은 사용하지 않아도 된다.
도시 \(1\)에서 도시 \(N\)까지 이동하는 데 필요한 최소 비용을 구하시오.
제약
\(2 \le N \le 100\,000\)
\(1 \le M \le 200\,000\)
\(1 \le a, b \le N\)
\(1 \le c \le 10^9\)
도시 \(1\)에서 도시 \(N\)까지 이동할 수 있는 경로가 항상 존재한다.
입력 형식
첫째 줄에 도시의 개수 \(N\)과 도로의 개수 \(M\)이 주어진다.
둘째 줄부터 \(M\)개의 줄에는 도로 정보 \(a\ b\ c\)가 주어진다.
이는 도시 \(a\)와 도시 \(b\)가 비용 \(c\)인 양방향 도로로 연결되어 있다는 뜻이다.
출력 형식
도시 \(1\)에서 도시 \(N\)까지 이동하는 데 필요한 최소 비용을 출력한다.
예제 1
입력
5 6
1 2 4
1 3 2
2 4 7
3 4 4
4 5 3
2 5 100출력
4설명
예제 설명 1
경로를 다음과 같이 이동할 수 있다.
1 → 2 → 5
비용은 원래 4 + 100 = 104이다.
이때 2 → 5 도로에서 무료 이동권을 사용하면 총 비용은
4 + 0 = 4
가 된다.
예제 2
입력
4 4
1 2 10
2 4 10
1 3 1
3 4 100출력
1문제 시리즈
문제 정보
anthony0506 작성
출처 anthony0506
태그
평가 및 의견
한 번의 무료 이동
개요
티어 투표 분포
골드 II
1
Log in to rate problems.
개별 의견
rip
골드 II
★★★★★
2026-06-05 21:49
풀이 제출
한 번의 무료 이동
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기