페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3876

이동 방해 1s 128MB

문제

농부 존은 매일 아침마다 집에서 헛간까지 농장을 가로질러 걸어갑니다. 농장에는 N개의 들판 (1 \le N \le 250)이 있고 들판을 연결하는 M개의 양방향 길 (1 \le M \le 25,000)이 있습니다. 농부 존의 집은 1번 들판에 있고, 헛간은 N번 들판에 있습니다. 어떤 들판 쌍도 여러 개의 중복된 경로로 연결되어 있지 않으며, 모든 들판이 길을 통해 연결되어 있습니다. 길마다 통행하는 데 각자 시간이 듭니다. 농부 존은 집에서 헛간까지 이동할 때 이동시간이 가장 빠른 방법으로 이동합니다.

항상 말썽을 부리는 농부 존의 소들은 그의 아침 일과를 방해하기로 결정했습니다. 그들은 농장의 M가지 길 중 정확히 한 곳에 건초 더미를 쌓아 길을 통행하는 데 걸리는 시간을 두 배로 늘릴 계획입니다. 소들은 농부 존의 집에서 헛간까지 가는 최단시간을 최대한 많이 늘리고 싶어합니다. 소들이 농부 존의 경로를 어떻게 방해할 지 결정하는 것을 도와주세요.


입력

첫째 줄에는 정수 N, M이 주어진다.

두 번째 줄부터 M개의 줄에는 정수 A_j, B_j, L_j가 주어진다. j번째 길이 A_i번 들판과 B_i번 들판을 연결하며 길을 이동하는 데 L_j 시간이 걸린다. (1 \le A_j, B_j \le N, A_j \neq B_j, 1 \le L_j \le 10^6)


출력

소들이 적절한 길 위에 건초 더미를 놓았을 때, 농부 존이 집에서 헛간까지 가는 최단시간의 증가량을 출력한다.


예제 

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2
2

입력 설명

농장에는 5개의 들판과 7개의 길이 있다. 농부 존이 집에서 헛간까지 가는 최단경로는 1-3-4-5이며 총 소요시간은 1+3+2=6이다.

해설

소들이 3번 들판과 4번 들판을 연결하는 길에 건초 더미를 놓아 소요시간을 6으로 만들었다면, 농부 존의 최단경로는 1-3-5로 총 소요시간은 1+7=8이 되어, 이전 최단경로보다 2만큼 시간이 더 걸리게 된다.



출처

USACO 2014 February Silver 2 / Gold 1

로그인해야 코드를 작성할 수 있어요.