레이팅 미적용매일 아침 농부 존은 일어나서 집에서 헛간까지 농장을 가로질러 걸어간다. 농장은 각각 길이가 정해진 M개의 양방향 길 (1 <= M <= 25,000)로 연결된 N개의 밭 (1 <= N <= 250)의 모음이다. 농부 존의 집은 밭 1에 있고 헛간은 밭 N에 있다. 어떤 밭 쌍도 여러 개의 중복된 길로 연결되어 있지 않으며, 적절한 길들의 수열을 따라 걸어서 농장의 임의의 두 밭 사이를 이동할 수 있다. 한 밭에서 다른 밭으로 이동할 때 농부 존은 항상 총길이가 최소인 길들의 수열로 이루어진 경로를 선택한다.
언제나처럼 말썽을 부리는 농부 존의 소들은 그의 아침 일과를 방해하기로 했다. 소들은 농장의 M개의 길 중 정확히 하나에 건초 더미 무더기를 쌓아 그 길의 길이를 두 배로 만들 계획이다. 소들은 농부 존의 집에서 헛간까지의 거리 증가량이 최대가 되도록 막을 길을 선택하고 싶다. 소들이 농부 존의 경로를 얼마나 늘릴 수 있는지 구하는 것을 도와주자.
문제 제공: Brian Dean
첫째 줄: 공백으로 구분된 두 정수 N과 M.
둘째 줄부터 1+M번째 줄까지: j+1번째 줄에 공백으로 구분된 세 정수 A_j B_j L_j로 j번째 양방향 길이 주어진다. A_j와 B_j는 그 길이 잇는 밭을 나타내는 범위 1..N의 인덱스이고, L_j는 길의 길이(범위 1...1,000,000)이다.
첫째 줄: 길 하나의 길이를 두 배로 만들어 얻을 수 있는 농부 존의 최단 경로 총길이의 최대 증가량.
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 > 2013-2014 > February > Gold