레이팅 미적용매일 아침 FJ는 잠에서 깨어 집에서 헛간까지 농장을 가로질러 걸어간다. 농장은 N개 (1 <= N <= 100)의 목초지가 M개 (1 <= M <= 10,000)의 양방향 길로 연결된 형태이며, 각 길에는 길이가 있다. FJ의 집은 목초지 1에 있고, 헛간은 목초지 N에 있다. 어떤 목초지 쌍도 여러 개의 중복된 길로 연결되어 있지 않으며, 적절한 길들을 따라 걸으면 농장의 임의의 두 목초지 사이를 이동할 수 있다. 한 목초지에서 다른 목초지로 이동할 때, FJ는 항상 총 길이가 최소인 길들의 경로를 선택한다.
언제나처럼 말썽을 꾸미는 농부 존의 소들은, FJ의 아침 일과를 방해하기로 했다. 소들은 농장의 M개의 길 중 정확히 하나에 건초 더미를 쌓아 그 길의 길이를 두 배로 만들 계획이다. 소들은 FJ의 집에서 헛간까지의 거리 증가량이 최대가 되도록 막을 길을 고르고 싶어 한다. 소들이 FJ의 경로를 얼마나 늘릴 수 있는지 구하는 것을 도와주자.
첫째 줄: 공백으로 구분된 두 정수 N (1 <= N <= 100)과 M (1 <= M <= 10,000).
둘째 줄부터 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 22Input details: There are 5 fields and 7 pathways. Currently, the shortest path from the house (field 1) to the barn (field 5) is 1-3-4-5 of total length 1+3+2=6.
Output details: If the cows double the length of the pathway from field 3 to field 4 (increasing its length from 3 to 6), then FJ's shortest route is now 1-3-5, of total length 1+7=8, larger by two than the previous shortest route length.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > December > Silver