레이팅 미적용매일 아침 FJ는 일어나서 집에서 축사까지 농장을 가로질러 걸어간다. 농장은 N개의 밭 (1 <= N <= 250)이 M개의 양방향 길 (1 <= M <= 25,000)로 연결된 구조이며, 각 길에는 길이가 있다. FJ의 집은 밭 1에 있고 축사는 밭 N에 있다. 어떤 두 밭도 여러 개의 중복된 길로 연결되어 있지 않으며, 임의의 두 밭 사이를 이동하는 것이 가능하다. 이동할 때 FJ는 항상 총 길이가 최소인 경로를 선택한다.
농부 존의 소들은 그의 아침 일과를 방해하기로 했다. 소들은 M개의 길 중 정확히 하나에 건초 더미를 쌓아 그 길의 길이를 두 배로 만들 계획이다. 소들은 집에서 축사까지 FJ가 이동하는 거리의 증가량이 최대가 되도록 막을 길을 고르고 싶어 한다. 소들이 FJ의 경로를 얼마나 늘릴 수 있는지 구하는 것을 도와주시오.
(이 문제는 USACO 2014 February 대회의 실버 2번 문제와 골드 1번 문제로 동일하게 출제되었다.)
첫째 줄에 공백으로 구분된 두 정수 N과 M이 주어진다.
둘째 줄부터 1+M번째 줄까지, j+1번째 줄에 j번째 양방향 길을 나타내는 공백으로 구분된 세 정수 A_j B_j L_j가 주어진다. A_j와 B_j는 그 길이 잇는 두 밭의 번호로 1..N 범위이며, L_j는 길의 길이로 1...1,000,000 범위이다.
길 하나의 길이를 두 배로 만들어 얻을 수 있는, FJ의 최단 경로 총 길이 증가량의 최댓값을 출력한다.
rblock.in · 출력을 쓸 파일 rblock.out5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 22Output details: Doubling the pathway from field 3 to 4 makes FJ's shortest route 1-3-5 of length 8, an increase of 2.
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > February > Silver